2つの再帰呼び出しによる再帰アルゴリズムの時間複雑度

Question

Generate all sequences of bits within Hamming distance t問題を解決する再帰アルゴリズムの時間複雑度を分析しようとしています。アルゴリズムは次のとおりです。

// str is the bitstring, i the current length, and changesLeft the 
// desired Hamming distance (see linked question for more) 
void magic(char* str, int i, int changesLeft) { 
     if (changesLeft == 0) { 
       // assume that this is constant 
       printf("%s\n", str); 
       return; 
     } 
     if (i < 0) return; 
     // flip current bit 
     str[i] = str[i] == '0' ? '1' : '0'; 
     magic(str, i-1, changesLeft-1); 
     // or don't flip it (flip it again to undo) 
     str[i] = str[i] == '0' ? '1' : '0'; 
     magic(str, i-1, changesLeft); 
} 

このアルゴリズムの時間複雑度はどのくらいですか？

---

自分はかなり錆び私が好きそれはこれに来て、ここで私は真実の近くに場所ではありません感じる私の試み、あるとき：nは、ビット列の長さである

t(0) = 1 
t(n) = 2t(n - 1) + c 
t(n) = t(n - 1) + c 
    = t(n - 2) + c + c 
    = ... 
    = (n - 1) * c + 1 
    ~= O(n) 

。

関連する質問：1、2

Answer 1

それは、指数です：

t(0) = 1 
t(n) = 2 t(n - 1) + c 
t(n) = 2 (2 t(n - 2) + c) + c   = 4 t (n - 2) + 3 c 
    = 2 (2 (2 t(n - 3) + c) + c) + c = 8 t (n - 3) + 7 c 
    = ... 
    = 2^i t(n-i) + (2^i - 1) c   [at any step i] 
    = ... 
    = 2^n t(0) + (2^n - 1) c   = 2^n + (2^n - 1) c 
    ~= O(2^n) 

または、WolframAlphaを使用して：それは指数関数的だhttps://www.wolframalpha.com/input/?i=t(0)%3D1,+t(n)%3D2+t(n-1)+%2B+c

理由は、あなたの再帰呼び出しが1で、問題のサイズを小さくしているが、あなたは、2つの再帰作っているということですコール。あなたの再帰呼び出しはバイナリツリーを形成しています。