Zeit Komplexität des rekursiven Algorithmus mit zwei rekursiven Aufrufe

Question

Ich versuche, die Zeit Komplexität eines rekursiven Algorithmus zu analysieren, der das Generate all sequences of bits within Hamming distance t Problem löst. Der Algorithmus ist dies:

// 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); 
} 

Was ist die zeitliche Komplexität dieses Algorithmus?

---

ich lieb ich ziemlich rostig, wenn es dazu kommt und hier ist mein Versuch, die ich fühle, ist nicht annähernd die Wahrheit:

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) 

wo n die Länge der Bit-Kette.

Verwandte Fragen: 1, 2.

Answer 1

Es ist exponentiellen:

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) 

Oder mit Wolframalpha: https://www.wolframalpha.com/input/?i=t(0)%3D1,+t(n)%3D2+t(n-1)+%2B+c

Der Grund ist es exponentiell ist, dass Ihre rekursive Aufrufe von 1 das Problem Größe reduzieren, aber Sie machen zwei rekursive Anrufe. Ihre rekursiven Aufrufe bilden einen binären Baum.