Probleme beim Verstehen des Hauptsatzes aus Jeffrey Ericksons Notizen

7

Ich schaue mir Jeffrey Ericksons Notizen zum Hauptsatz an (Seite 10).

Teil (b) des Satzes besagt, dass wenn , und k > 1, dann ist T (n) \ Theta (n ^ {\ log_b (a)}) . Aber ich bekomme ein anderes Ergebnis.T(n)=aT(nb)+f(n)af(nb)=kf(n)k>1Θ(nlogb(a))

Unter Verwendung von Rekursionsbäumen haben wir

T(n)=i=0logb(n)aif(nbi)=k=0logb(n)kif(n).

Wenn k<1 ist dies wie gewünscht f(n) . Wenn k=1 ist dies wie gewünscht logb(n)f(n) . Wenn jedoch k>1 ist, handelt es sich um eine aufsteigende geometrische Reihe, sodass der letzte Term dominiert. Dann haben wir

klogb(n)f(n)=nlogb(k)f(n),
was falsch ist; Die richtige Antwort lautet Θ(nlogb(a)) . Wo geht meine Argumentation aus dem Ruder und was ist die richtige Lösung?

Jede Hilfe wird geschätzt.

EDIT: Ich denke, meine Antwort ist tatsächlich richtig und entspricht Ericksons einfacherer Antwort. Man beachte, dass knf(n)=kn1af(nb)...=kan1f(nbk1)=anf(nbk). Daher ist klogb(n)f(n)=alogb(n)f(1)nlogb(a) .

Pensioniertes Konto
quelle

Antworten:

3

Sie können n ^ {\ log_b (k)} f (n) weiter vereinfachen nlogb(k)f(n).

Wir haben . Wenn , können wir diese Identität mal anwenden , um .akf(nb)=f(n)c=logb(n)c(ak)cf(1)

Alsonlogb(k)f(n)=nlogb(k)(ak)cf(1)=klogb(n)(ak)logb(n)f(1)=alogb(n)f(1)=Θ(nlogb(a))

orlp
quelle