تكرار مع وظيفة N مرات T ()

Question

الأسلوب الرئيسي يعمل بشكل جيد على مشاكل مثل $ t (n)= kt (an) + cn $ ، ولكنه لا يتعامل مع المشاكل $$ T (N)= n ^ {\ frac {} {} {\ frac {} {}} {3}}) + n ^ 2 $$ مع عدد الفروع لكل قسم هو وظيفة $ n $ .أتساءل عما إذا كان هناك حل جيد لهذا النوع من المشاكل، ليس لدي أي فكرة عن كيفية حل هذا، أي مساعدة موضع تقدير!

Answer 1

يمكنك استخدام الطريقة الأكثر ابتدائية التي تقوم فيها بتوسيع التكرار: \ ابدأ {align} T (n) &= n ^ 2 + n ^ {1/3} t (n ^ {2/3}) \\ &= n ^ 2 + n ^ {5/3} + n ^ {5/9} T (n ^ {4/9}) \\ &= n ^ 2 + n ^ {5/3} + n ^ {10/9} + n ^ {19/27} t (n ^ {8/27} ) \\ &= cdots \ END {محاذاة} هذا يشير إلى أن $ t (n)= o (n ^ 2) $ . في الواقع، دعونا نحاول إثبات الحث على أن $ t (n) \ leq cn ^ 2 $ : $$ T (n) \ leq n ^ 2 + n ^ {1/3} \ cdot cn ^ {4/3}= n ^ 2 \ left (1 + \ frac {c} {n ^ {1/3}}} \ حق)، $ التي ستكون على الأكثر $ cn ^ 2 $ لأي $ c> 1 $ و كبيرة بما يكفي $ n $ (اعتمادا على $ C $ ).

في الواقع، تحديد $ s (n)= t (n) - n ^ 2 $ لدينا $$ s (n)= n ^ {5/3} + n ^ {1/3} s (n ^ {2/3})، $ وهكذا تظهر نفس الحجة أن $ s (n)= o (n ^ {5/3}) $ وكذلك $ t (n)= n ^ 2 + o (n ^ {5/3}) $ . بنفس الطريقة، يمكننا الحصول على $ t (n)= n ^ 2 + n ^ {5/3} + O (n ^ {10/9}) $ ، وهلم جرا.