Résoudre la récurrence

Comment résoudre la relation de récurrence suivante?

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

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

recursion boulette de Mobius
la source

Qu'obtenez-vous si vous essayez

? Il semble que vous obtiendrez une borne inférieure de

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

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

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

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

Chandra Chekuri du

@ChandraChekuri Oh, c'est génial! Et il y a une limite supérieure de

: nous utilisons le

récurrence

fois, et obtenons que

. Ensuite, nous appliquons ce

fois et obtenons

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$

. Ainsi, l'écart entre la borne supérieure et la borne inférieure n'est que

dans l'exposant. C'est en fait suffisant pour mes besoins, mais je vais laisser la question ouverte au cas où quelqu'un le voudrait et serait en mesure de combler l'écart. Merci beaucoup, 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

Eh bien, la même astuce donne

, donc

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

Résoudre la récurrence

Réponses: