توضيح الدليل الذي ينطوي على حالة الانتظام في نظرية سيد

Question

كنت ذاهبا إلى النص مقدمة في الخوارزميات بواسطة Cormen et al. حيث صادفت العبارة التالية في دليل الحالة الثالثة من نظرية الماجستير.

(بيان نظرية الماجستير) دع $ a \ geqslant 1 $ و $ b> 1 $ أن تكون ثوابت، دع $ f (n) $ تكون وظيفة، ودع $ t (n) $ أن أعزم بالأعظم الصحي غير النظافة عن طريق التكرار (تقسم العودية مشكلة الحجم $ N $ في $ $ < / span> مشاكل حجم $ n / b $ كل ويستغرق $ f (n) $ for the تقسيم وتجمع)

$ t (n)= at (n / b) + f (n) $ ؛

حيث نرسم $ n / b $ يعني إما $ \ lceil b / n \ rceil $ أو $ \ llloor b / n \n\ rfloor $ . ثم $ t (n) $ لديه الحدود مقارب التالية:

1. إذا $ f (n)= o (n ^ {\ log_ba - \ epsilon}) $ لبعض $ \ Epsilon> 0 $ ، ثم $ t (n)=theta (n ^ {\ log_ba}) $ .

2. إذا كان $ f (n)=theta (n ^ {\ log_ba}) $ ، ثم $ t (n)=theta (n ^ {\ log_ba} \ lg n) $

3. إذا كنت $ f (n)=omega (n ^ {\ log_ba + \ epsilon}) $ لبعض $ \ Epsilon> 0 $ ، وإذا $ af (n / b) \ leqslant cf (n) $ لبعض $ C <1 $ وجميع Suf Fi كبير N، ثم $ t (n)=theta (f (n)) $ .

ل $ n $ حسب القوى الدقيقة من $ B $ نحن نقيد مجال T (N ) على النحو التالي:

$$ T (N)=Theta (1)، n= 1 $ $$ t (n)= at (n / b) + f (n)، n= b ^ i $$

الآن في إثبات نظرية ماجستير مع $ n $ كطاقة دقيقة من $ B $ التعبير عن $ t (n) $ يقلل إلى:

$$ t (n)=theta (n ^ {\ log_ba}) + \ sum_ {j= 0} ^ {\ log_bn -1} a ^ jf (n / b ^ j) $

href="https://i.stack.imgur.com/nzrdr.png" rel="nofollow noreferrer">

ثم يفترض المؤلفون ما يلي،

$$ g (n)=sum_ {j= 0} ^ {\ log_bn -1} a ^ jf (n / b ^ j) $

ثم لإثبات الحالة الثالثة لنظرية الماجستير، يثبت المؤلفون Lemma التالي،

lemma 1 : إذا كان $ a \ cdot f (n / b) \ leqslant c \ cdot f (n) $ لبعض ثابت $ C <1 $ وجميع $ n \ geqslant b $ ثم $ g (n)=theta (f (n)) $

يقولون ذلك:

تحت افتراضها أن $ c <1 $ "span class=" math-container "> $ n \ geqslant b $ ، لديهم $ a \ cdot f (n / b) \ leqslant c \ cdot f (n) \ يعني f (n / b) \ leqslant (c / a ) \ CDOT F (n) $

ثم التكرير $ J $ times gielt، $ f (n / b ^ j ) \ leqslant (c / a) ^ j \ cdot f (n) $

لم أتمكن من الحصول على الرياضيات المستخدمة وراء التكرار $ J $ times .

علاوة على ذلك، لم أستطع الحصول على المنطق وراء افتراض $ n \ geqslant b $ للحصول على الوضع الذي $ يجب أن تكون N $ كبيرة بما فيه الكفاية. (كما يقول نظرية الماجستير الثالثة.)

يستمر دليل الليمما كما يلي:

$$ f (n / b ^ j) \ leqslant (c / a) ^ j \ cdot f (n) \ IFF a ^ j \ cdot f (n / b ^ j) \ leqslant c ^ j \ cdot f (n) $ لذلك، $$ G (n)=sum_ {j= 0} ^ {\ log_bn -1} a ^ jf (n / b ^ j) $ $ \ leqslant \ sum_ {j= 0} ^ {\ log_bn -1} c ^ jf (n) $ $$ \ leqslant f (n) \ sum_ {j= 0} ^ {\ infty} c ^ j، $ ك $ c <1 $ لدينا سلسلة هندسية لانهائية $$= f (n) \ left (\ frac {1} {1-c} \ right) $ $$= O (F (n)) $ ك $ C $ هو ثابت. (لاحظ أن $ t (n)=omega (f (n

)) من مخطط العودية.)

ثم دليل المؤلفين دليل على الحالة الثالثة من نظرية الماجستير ل $ N $ كطاقة دقيقة من $ B $ < / span>:

lemma 2 : دع $ a \ geqslant 1 $ و $ b> 1 دولار ، إذا $ f (n)=omega (n ^ {\ log_ba + \ epsilon}) $ لبعض $ \ Epsilon> 0 $ ، وإذا كان $ af (n / b) \ leqslant cf (n) $ لبعض $ C <1 $ وجميع Suf Fi كبير N، ثم $ t (n)=theta (f (n)) $ .

حتى $$ t (n)=theta (n ^ {\ log_ba}) + g (n)=theta (n ^ {\ log_ba}) + \ theta (f (n))=theta (f (n)) $ ك $ f (n)=omega (n ^ {\ log_ba + \ epsilon} ) $

علاوة على ذلك في إثبات مماثل للحالة الثالثة من نظرية السيد العام العام (لا تفترض $ N $ حسب القوى الدقيقة من $ B $ ) هناك مرة أخرى يفترض الكتاب أن $ n \ geqslant b + b / (b-1) $ للذهاب مع وضع بما فيه الكفاية كبير $ n $ .

أنا لا أفهم تماما ما يجب أن تفعله القيمة المحددة ولماذا يفترض أن هذا مفترض ككافح $ n $

(أنا لم أعطي تفاصيل الوضع الثاني لأنني أشعر أنه يجب أن يكون شيئا مشابها للوضع الأول ولكن يمكن العثور عليه هنا

Answer 1

دعنا نبدأ بمسألة التكرار. افترض أن وظيفة $ f $ يرضي $$ f (n / b) \ leq (c / a) f (n). $ ثم يرضي أيضا $$ f (n / b ^ 2) \ leq (c / a) f (n / b) \ leq (c / a) ^ 2 f (n). $ يمكنك إثبات ذلك عن طريق التعريفي على أنه لجميع الأعداد الصحيحة $ t \ geq 0 $ ، $$ f (n / b ^ t) \ leq (c / a) ^ t f (n).

كما هو الحال بالنسبة لسؤالك الثاني، حول افتراض أن $ n $ كبير بما فيه الكفاية: والدليل هو مجرد قذرة. لا يمكنك افتراض أن $ f (n / b) \ leq (c / a) f (n) $ يحمل لجميع $ n \ geq b $ . في الواقع، في مقدمة الخوارزميات، الطبعة الثالثة، لا تجعل مثل هذا الافتراض للقضية حيث $ n $ هو قوة $ B $ .

يبدو أنها تجعل مثل الافتراض في حالة عامة $ n $ ، ولكن ما يقولون حقا هو أن عدم المساواة $ f (\ lceil n / b \ rceil) \ leq (c / a) f (n) $ فقط المنطقي فقط $ n \ ge b + ب / (B-1) $ . باستخدام فكرة إثبات الحالة الخاصة حيث $ n $ هي قوة $ B $ ، يمكنك إكمال دليل على الحالة العامة. ومع ذلك، أود أن أقترح بشدة تجاهل هذه التقنيات في الوقت الحاضر. The Master Theorem هو في الأساس حساب، ويمكنك الوثوق بالمؤلفين بأنه يعمل. لا شيء مثير للاهتمام مخفي تحت البساط.