So lösen Sie die Rekursion mit zwei separaten Konvergationsraten

Question

Was ist der richtige Weg, um den folgenden Rekursion zu lösen: $ t (n)= t (\ lceil \ frac {n} {2} \ RCEIL) + T (N-2) $

oder grundsätzlich jede Rekursion, die zwei Teile aufweist, die sich in einer anderen Rate zusammenlaufen.

Ich versuche, große $ o $ Näherung, so eng wie möglich, aber ich konnte es nicht mit einem "traditionellen" Ansatz herausfinden.

Answer 1

Wenn Sie die Anfangsbedingungen annehmen $ t (0)= 0 $ und $ t (1)= 1 $ dann erhalten Sie A018819 (bis zum Verschieben), was im Wesentlichen A000123 . Die Asymptotika sind bekannt, dass sie $ T (n)= n ^ {\ theta (\ \ log n)} $ sind. Die Referenzen unter dem zweiten Eintrag enthalten genauere asymptotische Informationen.

mehr explizit, A018819 erfüllt die Wiederholung $ A (2m + 1)= a (2m)= a (2m-1) + a (m) $ , mit $ A (0)= A (1)= 1 $ . Sie können induktiv zeigen, dass $ A (n)= t (n + 1) $ . In der Tat:

.
• wenn $ n= 2m + 1 $ dann $$ t (n + 1)= t (2m + 2 )= T (m + 1) + t (2m)= a (m) + a (2m-1)= a (2m)= a (2m + 1)= a (n). $$ < / li>
• wenn $ n= 2m $ dann $$ 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). $$