Rozwiąż rekurencję

Jak mogę rozwiązać następującą relację powtarzalności?

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

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

recursion pierożek Mobiusa
źródło

Co otrzymasz, jeśli spróbujesz

? Wygląda na to, że otrzymasz dolną granicę

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 Och, to świetnie! I jest górna granica

: używamy

rekurencji

razy i otrzymujemy

. Następnie stosujemy

razy i otrzymujemy

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$

. Tak więc różnica pomiędzy górnymi i dolnymi związany jest związany tylko

w wykładniku. To właściwie wystarcza do moich celów, ale pozostawię pytanie otwarte, na wypadek, gdyby ktoś chciał i był w stanie wypełnić lukę. Dziękuję bardzo, 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$

mobius dumpling

Cóż, ta sama sztuczka daje

, więc

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

Odpowiedzi:

@Chandra, @Emil i ja rozwiązaliśmy pytanie w komentarzach. Rozwiązaniem jest

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

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

Aby zobaczyć dolną granicę, zastosuj definicji rekurencji razy, aby uzyskać Użyj tej nierówności $\log n$

fa (n) = 2) fa (n - \log n) + fa (n - \log n - 1) + \dots + fa (n - 2) \log n) \geq \log n \cdot fa (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) \ .$

razy i otrzymujemy, że rozwiązaniem jest

n / \log n

$n / \log n$

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

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

$\log n$

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

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

n / \log n

$n / \log n$

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

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

pierożek Mobiusa
źródło