Come risolvere la ricorsione con due tassi di converge separati

Question

Qual è il modo corretto per risolvere la seguente ricorsione: $ t (n)= t (\ lceil \ frac {n} {2} \ rceil) + t (n-2) $

o fondamentalmente qualsiasi ricorsione con due parti che convergono in un tasso diverso.

Sto cercando di ottenere il grande $ o $ approssimazione, il più stretto possibile, ma non riuscivo a capirlo con nessun approccio "tradizionale". .

Answer 1

Se si prendono le condizioni iniziali $ t (0)= 0 $ e $ t (1)= 1 $ Allora ottieni A018819 (fino a Shift), che è essenzialmente A000123 . Gli asintotici sono noti per essere $ t (n)= n ^ {\ theta (\ log n)} $ . I riferimenti sotto la seconda voce contengono informazioni asintotiche più accurate.

Più esplicitamente, A018819 soddisfa la ricorrenza $ A (2m + 1)= A (2 m)= A (2m-1) + A (M) $ , con $ A (0)= A (1)= 1 $ . Puoi mostrarlo in modo induttivo che $ A (n)= t (n + 1) $ . In effetti:

.
• se $ n= 2m + 1 $ quindi $$ t (n + 1)= t (2m + 2 )= T (m + 1) + t (2m)= A (M) + A (2m-1)= A (2M)= A (2M + 1)= A (N). $$ < / li >.
• se $ n= 2m $ quindi $$ t (n + 1)= t (2m + 1)= t (2m + 1)= t T (m + 1) + t (2m-1)= A (M) + A (2m-2)= A (M) + A (2M-1)= A (2M)= A (N). $$