Löse die Wiederholung

12

Wie kann ich die folgende Wiederholungsbeziehung lösen?

f(n)=f(n1)+f(nlogn)
Mobius Knödel
quelle
5
Was bekommen Sie, wenn Sie versuchen ? Es scheint, dass Sie eine Untergrenze von 2 Ω ( n / log n ) erhalten . f(n)=2f(n-Logn)2Ω(n/Logn)
Chandra Chekuri
2
@ChandraChekuri Oh, das ist großartig! Und es gibt eine Obergrenze von : Wir verwenden das erneute Auftreten log n - mal, und erhalten , dass f ( n ) ( 1 + log n ) f ( n - log n ) . Dann wenden wir dieses n / log n- mal an und erhalten f ( n ) ( 1 + log n2O(nloglogn/logn)lognf(n)(1+logn)f(nlogn)n/logn . Die Lücke zwischen Ober- und Untergrenze ist also nur log log n im Exponenten. Dies ist eigentlich genug für meine Zwecke, aber ich lasse die Frage offen, falls jemand die Lücke schließen möchte und kann. Vielen Dank, Chandra! f(n)(1+logn)n/logn=2O(nloglogn/logn)loglogn
Möbius Knödel
4
Nun, der gleiche Trick ergibt , also ist f ( n ) = 2 Θ ( n log log n / log n ) . f(n)(logn)f(n2logn)f(n)=2Θ(nloglogn/logn)
Emil Jeřábek unterstützt Monica am

Antworten:

14

f(n)=2Θ(nloglogn/logn) .

logn

f(n)=2f(nlogn)+f(nlogn1)++f(n2logn)lognf(nlogn) .
Use this inequality n/logn times, and we get that the solution is 2Ω(nloglogn/logn).

To get the upper bound, use the recurrence logn times and get that

f(n)(logn+1)f(nlogn) .
Use this inequality n/logn times, and we get that the solution is 2O(nloglogn/logn).
mobius dumpling
quelle