Die Rekursion

7

Ich betrachte die Wiederholung die die Laufzeit eines nicht spezifizierten Algorithmus beschreibt (Basisfälle werden nicht geliefert).

T(n)=T(n/2)+T(n/3)+n,

Unter Verwendung der Induktion fand ich, dass , aber es wurde mir gesagt, dass dies nicht eng ist. Nehmen wir in der Tat induktiv an, dass für alle (und ausreichend große Werte von ) giltT(n)=O(nlogn)T(k)Cklogkk<nk

T(n)Cn2logn2+Cn3logn3+n=C56nlognn(C/2+Clog3/31).

Jetzt wähle ich groß genug für , und so wird der letzte Ausdruck von dominiert .C(C/2+Clog3/31)>0C56nlognCnlogn

Meine erste Frage ist, was ist eine engere Bindung daran?

Zweitens habe ich versucht, die Akra-Bazzi-Methode zu verwenden, um dies zu lösen. Lassen Sie also lösen. Dann ist ungefähr und (mit ) erhalte ich und so weiterp

(12)p+(13)p=1.
p=0.79g(n)=n
1ng(u)up+1du=1n1updu=11p(n1p1),

T(n)=Θ(np(1+11p(n1p1))).

Dies entspricht , also insgesamt , da . Meine zweite Frage ist, dass ich nicht wirklich glaube, dass linear ist. Was ist also bei meiner Anwendung von Akra-Bazzi schief gelaufen?Θ(np+11pn11pnp)Θ(n)p<1T

Freundliche Grüße.

HowDoICSharply
quelle

Antworten:

5

Wenn und , können wir zeigen, dass durch Induktion.T(1)6T(2)12T(n)6n

T(n)=T(n/2)+T(n/3)+n6(n/2)+6(n/3)+n=6n.

Allgemeiner sei eine Konstante, so dass und , dann können wir routinemäßig beweisen, dass . Obwohl es Ihnen unglaublich erscheinen mag, ist es wahr, dass c>6T(1)cT(2)2cT(n)cn

T(n)=O(n).

Intuitiv sind die Terme und nicht groß genug, um auf eine Potenz von eines größeren Exponenten anzuheben , da .12+13<1T(n/2)T(n/3)nn

Es ist nichts Falsches an Ihrer Anwendung der Akra-Bazzi-Methode, die uns sagt, dass .T(n)=Θ(n)

John L.
quelle
4

Sei . Dann erfüllt die Wiederholung Insbesondere wenn erfüllt, dann ist würde implizieren . Dies ist bei allen der Fall .S(n)=T(n)/nS(n)

S(n)12S(n2)+13S(n3)+1.
C
12C+13C+1C
S(n/2),S(n/3)CS(n)CC6

Yuval Filmus
quelle