Comment résoudre les récursions avec deux taux de convergence distincts
-
29-09-2020 - |
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".
La solution
Si vous prenez les conditions initiales T (0)= 0 $ ET $ T (1)= 1 $ alors vous obtenez A018819 (Up to Shift), qui est essentiellement
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). $$