كيفية حل العودية مع اثنين من معدلات تحويل منفصلة

Question

ما هي الطريقة الصحيحة لحل العودية التالية: $ t (n)= t (\ lceil \ frac {} \} {2} \ rceil) + t (n-2) $

أو أساسا أي recursion يحتوي على جزأين يتلقون بمعدل مختلف.

أحاول الحصول على $ O $ التقريب، ضيق قدر الإمكان، لكنني لم أستطع معرفة ذلك مع أي نهج "تقليدي".

Answer 1

إذا كنت تأخذ الشروط الأولية $ t (0)= 0 $ و $ t (1)= 1 دولار ثم تحصل على A018819 (حتى التحول)، وهو أساسا a000123 . من المعروف أن النساجات هي $ t (n)= n {\ theta (\ theta (\ log n)} $ . تحتوي المراجع الموجودة تحت الإدخال الثاني على معلومات مقارب أكثر دقة.

أكثر صراحة، A018819 يرضي التكرار $ a (2m + 1)= a (2m + 1)= a (2m-1) + a (m) $ ، مع $ A (0)= a (1)= 1 $ . يمكنك إظهار حالة $ A (n)= t (n + 1) $ . في الواقع:

• إذا $ n= 2m + 1 $ ثم $$ t (n + 1)= t (2m + 2) )= t (m + 1) + t (2m)= a (m) + a (2m-1)= a (2m-1)= a (2m + 1)= a (n). $ < / لى>
• إذا $ n= 2m $ ثم $$ T (N + 1)= T (2M + 1)= T (M + 1) + T (2M-1)= a (m) + a (2m-2)= a (m) + a (2m-1)= a (2m-1)= a (n). $$