Lösen der Wiederholung T (n) = 3T (n-2) mit iterativer Methode

7

Es ist schon eine Weile her, dass ich eine Wiederholung lösen musste und ich wollte sicherstellen, dass ich die iterative Methode zur Lösung dieser Probleme verstehe. Gegeben:

T(n)=3T(n2)

Mein erster Schritt bestand darin, Begriffe iterativ zu ersetzen, um zu einer allgemeinen Form zu gelangen:

T(n2)=3T(n22)=3T(n4)
T(n)=33T(n4)

was zur allgemeinen Form führt:

T(n)=3kT(n2k)

Jetzt löse ich n2k=1 zum kDies ist der Punkt, an dem die Wiederholung aufhört (wo T(1)) und geben Sie diesen Wert ein (n/21/2=k) in die allgemeine Form:

T(n)=3n/21/2
T(n)=O(3n)

Bei diesem letzten Schritt bin ich mir nicht sicher:

Ich würde das einfach als "argumentieren" n man kann ignorieren 1/2 und n/2n? Ist diese Annahme richtig?

wpp
quelle

Antworten:

7

Beachten Sie, dass 3n/21/2=133n/2=133n. Also die12 in der Tat wird ein konstanter Faktor, der von der absorbiert wird O(), aber n2 im Exponenten ändert sich die Basis und durch Ändern der Basis ändert sich die O-Klasse.

Die richtige Antwort lautet also T(n)=O(3n/2)=O(3n).

FrankW
quelle
Vielen Dank an @FrankW und @Jared! Ich habe diese Antwort als richtig markiert, da sie eine Erklärung enthält (das Ändern der Basis ändert die O-Klasse).
wpp
6

Bis zum letzten Schritt war alles korrekt ... Sie fanden:

T(n)3n212=(3n1)12=13(3)n
Jared
quelle