Comment résoudre les récursions avec deux taux de convergence distincts

Question

Quelle est la bonne façon de résoudre la récursion suivante: $ t (n)= t (\ lceil \ frac {n} {2} \ rcil) + t (n-2) $

ou essentiellement une récursion qui a deux parties convergent d'un taux différent.

J'essaie d'obtenir BIG $ O $ Approximation, aussi étroite que possible, mais je ne pouvais pas le comprendre avec une approche "traditionnelle".

Answer 1

Si vous prenez les conditions initiales T (0)= 0 $ ET $ T (1)= 1 $ alors vous obtenez A018819 (Up to Shift), qui est essentiellement A000123 . Les asymptotiques sont connus pour être $ t (n)= n ^ {\ theta (\ journal n)} $ . Les références sous la deuxième entrée contiennent des informations asymptotiques plus précises.

plus explicitement, A018819 satisfait la récurrence $ A (2m + 1)= A (2m)= A (2m-1) + a (m) $ , avec $ A (0)= A (1)= 1 $ . Vous pouvez montrer de manière inductive que $ a (n)= t (n + 1) $ . En effet:

• si $ n= 2m + 1 $ alors $$ t (n + 1)= t (2m + 2 )= T (m + 1) + t (2m)= a (m) + a (2m-1)= A (2m)= A (2m + 1)= A (n) $$ < / li>
• si $ n= 2m $ alors $$ t (n + 1)= t (2m + 1)= T (m + 1) + t (2m-1)= A (m) + a (2m-2)= A (m) + A (2m-1)= A (2m)= A (N). $$