Zeit Komplexität: Haben diese beiden Codes die gleiche Zeit Komplexität oder nicht?

Question

Ich lese ein Buch mit dem Namen knacken das Coding-Interview 6. Ausgabe. Im Hinblick auf die Zeitkomplexität, gibt es einen Beispielcode für rekursive Runtimes (Seite 44):

int f(int n) { 
if (n <= 1){ 
    return 1; 
} 
return f(n - 1) + f(n - 1); 
} 

Ich denke mir, wenn der folgende Code, der das gleiche numerische Ergebnis erzeugt die gleiche Zeitkomplexität haben würde? Ich denke, es wäre nicht?

int f(int n) { 
    if (n <= 1){ 
     return 1; 
    } 
    return 2 * f(n - 1); 
    } 

zusätzliche: die folgenden ist der Kontext, der (ersten) -Code in dem Buch:

Answer 1

Executing eine Funktion zweimal nicht das gleiche ist wie der Wert der Funktion multipliziert wird bei dieser Punkt mit 2. Denken Sie an eine Funktionsausführung als ein paar Anweisungen, die ausgeführt werden. So

wenn Sie das tun:

return f(n-1) + f(n-1) //In your definition of f(n) 

f(n) zu berechnen, muss f(n-1) zweimal berechnet werden. Und dann f(n-1) zu berechnen, muss f(n-2) zweimal nacheinander berechnet werden. So wachsen die Ausführungsaufrufe in Form eines Baumes und multiplizieren sich zweimal auf jeder Ebene. Sieht so etwas wie dies in bildlichem Format:

jedoch in der zweiten Definition wo:

return 2 * f(n-1) //In your definition of f(n) 

f(n) zu berechnen, berechnen wir f(n-1)einmal nur dann wir es einfach multiplizieren mit 2, die die Gesamtkomplexität des Programms in Bezug auf die Nummer n nicht beeinflusst. Beachten Sie, dass wir nicht überall Zwischenwerte von f(n-1) oder f(n-2) sparen und das ist, warum ich sage, dass sie jedes Mal berechnet werden, sonst wäre das Szenario gewesen different.So in Ihrem Fall, geht das Programm so etwas wie:

Versuchen Sie, Ihre Funktionsdefinitionen erneut zu durchlaufen und visualisieren Sie sie in Form von Anweisungen, die bei jeder Iteration ausgeführt werden. Sie werden zwei ähnliche Bilder im Kopf haben.

Ich hoffe, es bringt Sie in die richtige Richtung.