العثور على القضية الأساسية ل t (n)= t (n - a) + t (a) + cn

Question

كنت حل التكرار باستخدام طريقة شجرة الإصابة: $$ t (n)= t (n - a) + t (a) + cn §

عندما بدأت حلها، يمكنني بسهولة أن أختتم حقيقة أن $ t (a) $ سيكون لديك حساب التكلفة الإجمالية في شكل:

$$ H * CA $ $ لكنني لم أستطع معرفة كيفية حل القضية الأساسية.

أعرف أن $ t (na) $ ستكون في حالة قاعدة عند $ n= $ n= a $ .

ولكن كيفية حساب الارتفاع $ H $ من التكرار. أعرف أن القضية الأساسية يمكن تعريفها على النحو التالي: $$ N-IA= 0 $$

لقد رأيت الأمثلة السابقة في الكتاب مقدمة في الخوارزميات يقتبس:

حجم subprobroblem لحجم عقدة عند العمق $ i $ $ هو $ n / 4 ^ i $ وبعد وهكذا، Subproblem حجم يضرب $ n= 1 $ عندما $ n / 4 ^ i= 1 $ أو، معادل، عندما $ i=log_4 n $

للحصول على التكرار: $ t (n)= 3t (n / 4) + cn ^ 2 $

لذلك، القادمة إلى النقطة التي ستكون الحالة الأساسية مثل حجم المشكلة الفرعية يضرب $ n=؟ $ كما هو الحال في المثال أعلاه.

هل سيكون $ n= $ ؟

يرجى تصحيح لي إذا كنت مخطئا. شكرا لك.

Answer 1

كل $ 0 \ le k \ le a a $ غلة الحالة الأساسية $ t (k) $ وبعد إذا كنت تحاول حل التكرار Big-o، فقد تفترض ذلك جيدا أن هناك بعض $ C $ حيث $ t (k) \ le c $ لكل حالة قاعدة $ k $ .سوف يساعد في جعل الحساب أسهل قليلا