Löse die Wiederholung

Wie kann ich die folgende Wiederholungsbeziehung lösen?

f (n) = f (n - 1) + f (n - \log n)

$f(n) = f(n-1) + f(n - \log n)$

recursion Mobius Knödel
quelle

Was bekommen Sie, wenn Sie

versuchen ? Es scheint, dass Sie eine Untergrenze von

f (n) = 2 f (n - \log n)

$f(n) = 2f(n - \log n)$

2^{Ω (n / \log n)}

$2^{\Omega(n/\log n)}$

Chandra Chekuri

@ChandraChekuri Oh, das ist großartig! Und es gibt eine Obergrenze von

: Wir verwenden das erneute Auftreten

- mal, und erhalten , dass

. Dann wenden wir dieses

mal an und erhalten

2^{O (n \log \log n / \log n)}

$2^{O(n \log \log n / \log n)}$

\log n

$\log n$

f (n) \leq (1 + \log n) f (n - \log n)

$f(n) \le (1 + \log n) f(n - \log n)$

n / \log n

$n / \log n$

. Die Lücke zwischen Ober- und Untergrenze ist also nur

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) \leq (1 + \log n)^{n / \log n} = 2^{O (n \log \log n / \log n)}

$f(n) \le (1 + \log n)^{n / \log n} = 2^{O(n \log \log n / \log n)}$

\log \log n

$\log \log n$

Möbius Knödel

Nun, der gleiche Trick ergibt

, also ist

f (n) \geq (\log n) f (n - 2 \log n)

$f(n)\ge(\log n)f(n-2\log n)$

f (n) = 2^{Θ (n \log \log n / \log n)}

$f(n)=2^{\Theta(n\log\log n/\log n)}$

Emil Jeřábek unterstützt Monica am

Antworten:

f (n) = 2^{Θ (n \log \log n / \log n)} .

$f(n) = 2^{\Theta(n \log \log n / \log n)} \ .$

$\log n$

f (n) = 2 f (n - \log n) + f (n - \log n - 1) + \dots + f (n - 2 \log n) \geq \log n \cdot f (n - \log n) .

$f(n) = 2f(n - \log n) + f(n - \log n - 1) + \ldots + f(n - 2 \log n) \ge \log n \cdot f(n - \log n) \ .$ Use this inequality

n / \log n

$n / \log n$ times, and we get that the solution is

2^{Ω (n \log \log n / \log n)}

$2^{\Omega(n \log \log n / \log n)}$ .

To get the upper bound, use the recurrence $\log n$ times and get that

f (n) \leq (\log n + 1) \cdot f (n - \log n) .

$f(n) \le (\log n + 1) \cdot f(n - \log n) \ .$ Use this inequality

n / \log n

$n / \log n$ times, and we get that the solution is

2^{O (n \log \log n / \log n)}

$2^{O(n \log \log n / \log n)}$ .

mobius dumpling
quelle