تحديد أسوأ تعقيد خوارزمية

Question

يمكن للشخص يرجى شرح لي كيف يمكن للمرء أن تحديد أسوأ تعقيد خوارزمية.وأنا أعلم أن نحن بحاجة إلى استخدام المعادلة ث(ن) = max{t(I)|أنا عنصر د) ، حيث D هو مجموعة من المدخلات من الحجم n.لا حساب عدد العمليات التي تجرى لكل عنصر أنا ثم تأخذ ماكس ؟ ما أسهل طريقة هي هناك لتحقيق هذا الهدف ؟

Answer 1

وانطلاقا من المعادلة يفكر في ذلك إلى الوراء قليلا. ما يهتمون حقا هو التدرجية، أو، ما هو ذاهب الى القيام به كما يمكنك زيادة حجم المدخلات.

إذا يكون مجرد حلقة، على سبيل المثال، لديك O (ن) وقت تعقيد الخوارزمية. إذا كان لديك حلقة في حلقة أخرى على الرغم من أنه يصبح O (ن ^ 2)، لأنه يجب القيام به الآن ن ^ 2 أشياء كثيرة لإدخال أي حجم ن.

وعندما كنت أتحدث عن أسوأ الأحوال، كنت تتحدث عادة عن خوارزمية قطعية غير، حيث قد يكون لديك حلقة التي يمكن أن تتوقف قبل الأوان. ما تريد القيام به لهذا نفترض الأسوأ والتظاهر وحلقة تتوقف في وقت متأخر ممكن. حتى إذا كان لدينا:

<اقتباس فقرة>   

ول(كثافة العمليات ط = 0؛ ط <ن، ط ++) {      ل(الباحث ي = 0؛ ي <ن، ي ++) {         إذا (راند () 0،5>) ي = ن.      }   }

ونحن أن أقول أن أسوأ الحالات هي O (ن ^ 2). على الرغم من أننا نعلم أنه من المحتمل جدا أن الحلقة الوسطى وأوقفت في وقت مبكر، ونحن نتطلع لأسوأ أداء ممكن.

Answer 2

هذه المعادلة هو أكثر من تعريف من خوارزمية.

لا الخوارزمية في السؤال يهمني أي شيء آخر من حجم مدخلات ؟ إذا لم يكن ثم حساب ث(ن) هو "السهل".

إذا كان كذلك, في محاولة للتوصل إلى المرضية الإدخال.على سبيل المثال, مع فرز سريع قد يكون واضحا إلى حد ما أن فرز الإدخال المرضية ، يمكنك القيام ببعض عد أن نرى أنه يأخذ O(n^2) الخطوات.عند هذه النقطة يمكنك إما

1. يقولون أن المدخلات الخاصة بك هو "الحد الأقصى" المرضية
2. يحمل مطابقة العلوي على وقت التشغيل على أي الإدخال

مثال #1:

كل تمريرة من فرز سريع سوف يضع المحورية في المكان المناسب ، ثم recurse على قسمين.(handwave التنبيه) أسوأ الأحوال أن يكون بقية مجموعة على جانب واحد من محور.فرز الإدخال يحقق هذا.

مثال رقم 2:

كل تمريرة من فرز سريع يضع المحورية في المكان الصحيح حتى لا تكون هناك أكثر من س(ن) يمر.كل تمر لا يتطلب أكثر من O(n) العمل.مثل أي مدخل يمكن أن يسبب فرز سريع يستغرق أكثر من O(n^2).

في هذه الحالة رقم 2 أسهل بكثير.