Lösen

8

Einführung in Algorithmen , 3. Ausgabe (S. 95) enthält ein Beispiel für die Lösung der Wiederholung

T(n)=3T(n4)+nlog(n)

durch Anwendung des Hauptsatzes.

Ich bin sehr verwirrt darüber, wie es gemacht wird. Also, erste Schritt besteht darin, mit .a=3,b=4,f(n)=nlog(n)
nlogba=nlog43=O(n0.793)f(n)

Ich habe keine Ahnung, wie sie das verglichen haben. Das Buch erklärt:

f(n)=Ω(nlog43+ϵ) , wobei , Fall 3 gilt, wenn wir zeigen können, dass die Regelmäßigkeitsbedingung fürϵ0.2f(n).

Gefolgt von:

Für ausreichend großes n gilt Folgendes:af(nb)=3(n4)log(n5)(34)nlogn=cf(n) for c=34.

Woher kommt ?3(n4)

Newprint
quelle

Antworten:

11

Wenn unsere Wiederholung die Form , müssen wir, um den "dritten Fall" der Master-Methode zu verwenden, den folgenden Halt haben:T(n)=aT(n/b)+f(n)

f(n)=Ω(nlogba+ϵ) für einige und wenn für eine Konstante und alle ausreichend groß dann istϵ>0af(n/b)cf(n)c<1nT(n)=Θ(f(n))

Unsere Wiederholung ist definiert als

T(n)=3T(n/4)+nlogn.

Per Definition haben wir .a=3,b=4,f(n)=nlogn

Wir müssen nun zeigen, dass polynomiell größer als . Das ist der Teil " " von oben. Durch Definieren von erreicht. Der Grund dafür ist, dass und .f(n)nlogbaf(n)=Ω(nlogba+ϵ)ϵ0.2log430.793f(n)=Ω(n0.793+ϵ)

Wir müssen zeigen, dass die Regelmäßigkeitsbedingung erfüllt. Das ist der Teil " für eine Konstante und alle ausreichend großen ".f(n)af(n/b)cf(n)c<1n

Wir stecken einfach unsere Werte von , um zu erhalten:Wir haben nur das " " in und " " eingesteckt.a,b

af(n/b)=3(n/4)log(n/4).
nf(n)n/4

Um dies besser sichtbar zu machen, sei und beobachte, dass . Wenn wir mit tauschen, haben wir wobei .k=n/4af(k)=aklogkkn/4

3(n/4)log(n/4)(3/4)nlogn=cf(n)
c=3/4

Damit sind unsere notwendigen Anforderungen erfüllt und wir haben .T(n)=Θ(nlogn)

Nicholas Mancuso
quelle
1
Vielen Dank für die ausführliche Antwort. Also ist polynomisch als ? Ich habe wahrscheinlich die Bedeutung von "polynomial" falsch verstandenn0.793n1logn
Newprint
1
Das Polynom ist in diesem Fall . n10.793=n0.217
JeffE
@newprint Polynomial größer bedeutet nur, dass der Unterschied zwischen den beiden mindestens eine (möglicherweise gebrochene) Potenz von , nicht irgendeine kleinere Funktion wie . Insbesondere ist es genau die Bedingung für den "dritten Fall", dassn(logn)f(n)=Ω(nlogbnnϵ). Es ist das ExtranϵFaktor, der es polynomial größer macht. Und wie JeffE in diesem Fall betonte,ϵ=.217.
Joe
Könnten wir gewählt haben ϵ=0.00000001? So weit ich das verstehef(n) ist schon Ω(n0.793) Warum müssen wir also hinzufügen? 0.2?
Yos
Ist Big Omega nicht eine Untergrenze für die Laufzeit, so dass "asymptotocial gleich oder größer als" statt "polynomial größer als ..." sein sollte?
mLstudent33