algorithm - この再帰関係の解き方: T(n) = 2T(n/2) + 1

Question

この再帰関係で困っています。

T(n) = 2T(n/2) + 1

の答えを得るためにこれを解決する方法を説明するのを手伝ってくれる人はいO(n)ますか?

Answer 1

簡単にするために、2 のべき乗であると仮定しましょうn。たとえば、ifn = 8と基本ケースT(0) = 0then の再帰呼び出しのツリーは次のようになります。

                       1                                n = 8, depth 0
                      / \
                     /   \
                    /     \
                   /       \
                  /         \
                 /           \
                /             \
               /               \
              /                 \
             /                   \
            /                     \
           1                       1                    n = 4, depth 1
          / \                     / \
         /   \                   /   \
        /     \                 /     \
       /       \               /       \
      /         \             /         \
     1           1           1           1              n = 2, depth 2
    / \         / \         / \         / \
   /   \       /   \       /   \       /   \
  1     1     1     1     1     1     1     1           n = 1, depth 3
 / \   / \   / \   / \   / \   / \   / \   / \
0   0 0   0 0   0 0   0 0   0 0   0 0   0 0   0         n = 0, depth 4

ツリーにはlog(n) + 1、最下位レベルをカウントしないレベルがあります。これは、このレベルの各ノードにコストがあるため0です。を計算するT(n)には、この場合T(8)、ツリー内のすべてのものを合計する必要があります。

深さにノードがあり、それぞれのコストが等しいことに注意しiて2^iください1。

したがって、ツリー内の 1 の合計の式は次のとおりです。

sum [from i = 0 to log(n)] 2^i

これは と の等比級数でa_1 = 1、q = 2最初の値の合計を知りたいとしlog(n) + 1ます。これは次の式で与えられます。

(1 - 2^(log(n) + 1)) / (1 - 2) = 2n - 1

の場合n = 8、結果は15です。

これがお役に立てば幸いです。

Answer 2

このタイプの再帰は、Master theoremを使用して解決されます。

あなたの場合a = 2、b = 2そしてf(n) = 1。つまりc = log2(2) = 1、O(n^1) > O(1)3 番目のケースに該当するため、複雑さはO(n)です。