Решите повторение

Как я могу решить следующую рекуррентную связь?

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

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

recursion пельмени мобиус
источник

Что вы получите, если вы попытаетесь

? Похоже, что вы получите нижнюю границу

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

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

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

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

Чандра Чекури

@ChandraChekuri О, это здорово! И есть верхняя граница

: мы используем

повторений

раз и получаем, что

. Затем мы применяем это

раз и получаем

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$

. Таким образом, разрыв между верхней и нижней границами составляет только

в показателе степени. На самом деле этого достаточно для моих целей, но я оставлю вопрос открытым, если кто-то захочет и сможет сократить разрыв. Большое спасибо, Чандра!

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$

клецки мобиуса

Ну, тот же трюк дает

, поэтому

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)}$

Эмиль Йержабек

Решите повторение

Ответы: