اختيار ثابت للخطوة الأخيرة في طريقة الاستبدال $ T (N)= 5T (N / 4) + N ^ 2 $

Question

أحسب حلا لعلاقة تكرار، لكنني لست متأكدا من ما يجب أن يكون الثابت للخطط الأخير لعقد.

$ t (n)= 5t (n / 4) + n ^ 2 $

تخمين: $ t (n)= o (n ^ 2) $

prove: $ t (n) \ leq cn ^ 2 $

انهيار

$ t (n) \ leq 5 (c (n / 4) ^ 2) + n ^ 2 $

$= (5/16) cn ^ 2 + n ^ 2 $

$ \ leq cn ^ 2 $

للحصول على الخطوة الأخيرة لعقد لست متأكدا من أن تكون قيمة C - بسبب (5/16).سيكون تخميني C>= 1 وأنا لست متأكدا مما إذا كان ذلك سيعقد.

Answer 1

ثابت $ C $ يحتاج إلى إرضاء $$ \ FRAC {5} {16} c n ^ 2 + n ^ 2 \ leq c n ^ 2، $ هذا هو، $$ \ frac {5} {16} c + 1 \ leq c.$ نأمل أن تتمكن من تحديد مجموعة الثوابت $ C $ من أجل راضي هذا عدم المساواة.

Answer 2

$$ t (n)= 5t \ left (\ frac {n} {4} \ right) + n ^ 2= 5 ^ 2t \ left (\ frac {n} {4 ^ 2} \ right) + \ left (\ frac {} {} {16} {16} + 1 \ right) n ^ 2= \\= 5 ^ 3t \ left (\ frac {n} {4 ^ 3} \صحيح) + \ left (\ left (\ frac {} {} {} {16} \ right) ^ 2 + \ frac {5} {16} +1 \ right) n ^ 2=cdots= \\ = 5 ^ kt \ left (\ frac {n} {4 ^ k} {{^ k}} \ right) + \ left (\ left (\ frac {} {}} {16} \ right) ^ {k-1} + \ cdots + \ frac{5} {16} +1 \ right) n ^ 2 $$ إذا كان لديك بعض الشرط الأولي ل $ t (1) $ ، ونحن نفترض $ n= 4 ^ k \ leftrightrow k=\ log_ {4} n $ ، ثم نحصل عليها $$ t (n)= 5 ^ kt (1) + n ^ 2 \ frac {11} {11} {} \ {{{{{{} {5}} \ right) ^ {k-1} \ right) \ in O (n ^ 2) $