للاختيار في أسوأ الحالات الخطية وقت الغموض في النظر في $ N $ التي $ t (n)= o (1) $ and $ t (n) \ leq cn $

Question

كنت أذهب من خلال إدخال النص إلى الخوارزميات بواسطة cormen et. آل. حيث صادفت العلاقة المتكررة لتحليل تعقيد الوقت للخوارزمية المحددة الخطية وشعرت أن بعض الأشياء التي لا تطابق الاحترام فيما يتعلق بمجموعة $ n $ ، حجم الإدخال الذي $ t (n) $ يفترض $ O (1) $ و $ CN في طريقة الاستبدال.

تفاصيل النص كما يلي:

---

يمكننا الآن تطوير تكرار لأسوأ الحالات $ t (n) $ من الخوارزمية المحددة. الخطوات 1، 2، و 4 تأخذ $ O (n) $ الوقت. (الخطوة 2 تتكون من $ O (n) $ o (n) $ نداءات الإدراج فرز على مجموعات من الحجم $ o (1) $ <1) $ <1) / span> الخطوة 3 يستغرق بعض الوقت $ t (\ lceil n / 5 \ rceil) $ ، والخطوة 5 يستغرق وقتا في معظم $ t (7n / 10 + 6) $ ، على افتراض أن T متزايد رتابة. نحن نجعل الافتراض، والذي يبدو غير مشترك في الأول، أن أي مدخلات أقل من 10 دولارات $ تتطلب العناصر $ O (1) $ الوقت؛ أصل السحر ثابت $ 140 $ واضح قريبا. $ ^ \ dagger $ يمكننا بالتالي الحصول على التكرار

$$ t (n) \ leq \ ادبت {cates} o (1) & \ quad \ text {en. $ n <140 $ $ $ ^ \ ddagger $} \\ T (\ lceil n / 5 \ rceil) + t (7n / 10 + 6) + o (n) & \ quad \ text {en. $ n \ geq 140 $ $ ^ \ | $} \\ \ نهاية {الحالات} $

نعرض أن وقت التشغيل هو خطي عن طريق الاستبدال. أكثر تحديدا، وسوف نظهر أن $ T (n) \ leq CN $ للحصول على بعضها ثابتا كبيرا $ C $ و جميع $ n> 0 $ . نبدأ بافتراض أن $ t (n) \ leq cn $ للحصول على بعضها بشكل مناسب كبير $ c $ و جميع $ N <140 $ $ ^ {\ dagger \ dagger} $ ؛ يحمل هذا الافتراض إذا $ C $ كبير بما فيه الكفاية. نحن أيضا اختيار ثابت مثل هذه الوظيفة الموصوفة بواسطة $ O (n) $ (n) $ المصطلح أعلاه (والتي تصف المكون غير الرديء في وقت تشغيل الخوارزمية ) يحدها أعلاه بواسطة لجميع $ n> 0 $ . استبدال هذه الفرضية الاستقرارية في الجانب الأيمن من التكرار

$$ t (n) \ leq c \ lceil n / 5 \ rceil + c (7n / 10 + 6) + an $$

$$ \ leq cn / 5 + c + 7cn / 10 + 6c + an $$

$$= 9CN / 10 + 7C + A $

$$= CN + (- CN / 10 + 7C + AN). $$

وهو في معظم $ CN إذا

$$ - CN / 10 + 7C + an \ leq 0. \ Tag 1 $$

$$ \ IFF C \ GEQ 10A (N / 70)) \ رباعية \ Text {متى n> 70} $

لأننا نفترض أن $ n \ geq 140 $ $ ^ {\ ddagger \ ddager} $ لدينا $ n / (n-70) \ leq 2 $ وكذلك اختيار $ c \ geq 20a $ سوف ترضي عدم المساواة $ (1) $

---

$$ \ dagger \ text \ text {يتوافق البيان هنا مع $ \ ddager $ في العلاقة المتكررة} $

$$ \ dagger \ dagger \ text \ text {هذا البيان هنا لا يمتثل مع $ \ | $ في العلاقة المتكررة} $

$$ \ ddager \ ddager \ text \ text {the البيان هنا يتوافق مع $ \ | $ في العلاقة المتكررة} $

---

لم أستطع فهم هذا التناقض تماما، ومع ذلك، لم أشمل الخوارزمية بأكملها (متوفرة في قسم CLRS 9.3 $ $ ) ولكن إذا كانت هناك حاجة إلى ذلك، فيرجى القول يجب أن أدرجها كذلك.

Answer 1

يبدو أن $ \ dagger \ dagger $ يتوافق مع $ \ | $ .تحتاج فقط إلى اختيار $ C $ أكبر من أو يساوي $ \ gamma $ مخفي في $ o (1) $ التدوين في تعريف $ t (n) $ for $ n <140 $ (أي، الخط الذي تم وضع علامة مع $ \ ddager $ ).

بعد ذلك، لأي $ n \ in \ {1، \ dots، 139 \} $ ، لديك $T (N) \ Le \ Gamma \ Le C \ Le CN $ ، حسب الرغبة.