أسوأ حالة مقابل o (n)

Question

هل هناك فرق بين البيان "أسوأ وقت تشغيل في حالة خوارزمية A" و "وقت تشغيل الخوارزمية A I IS o (n)"؟

ما أعتقد أنه "لا يوجد فرق" لأن أسوأ حالات هو وقت تشغيل الذروة الذي يمكن أن تستغرقه الوظيفة ، o (n) يعني أن الوظيفة "تحدها". كلاهما يعطي نفس المعنى.

آمل أن يكون منطقي صحيحًا.

Answer 1

هناك اختلاف.

الخوارزمية هي O (F) ليست دقيقة: يجب أن تقول أن alogirthm هو O (و) في أفضل/أسوأ/حالة من الجاذبية. يمكنك القول أن هذا هو O (و) عندما يكون أفضل وأسوأ وشفاء هو نفسه ، لكن هذا ليس شائعًا جدًا.

Answer 2

وأنا أتفق مع مشاعرك ، ولكن هناك خوارزميات مشتركة (Quicksort على سبيل المثال) التي لديها وقت متوقع أفضل بكثير من أسوأ وقت لها. يمكنك المطالبة بـ Quicksort هي O (n^2) أسوأ حالة ، لكنك لا تزال تتوقع أن تكون O (n*log n) دائمًا (على الأقل لتنفيذ جيد).

كما أنه معقد مع الخوارزميات التي أطفأت السلوك. قد تحصل على O (n) أو o (log n) لعملية واحدة معينة ، ولكن العديد من العمليات على التوالي ستكون دائمًا o (1) بالمعنى المطفأ. تعتبر الأشجار المتوقفة وأشجار الأصابع أمثلة جيدة في هذه الفئة.

Answer 3

عادة ما يكون وقت التشغيل كتدبير مطلق أقل أهمية من كيف يزداد هذا الوقت عند إضافة المزيد من البيانات. على سبيل المثال ، يُقال إن الخوارزمية التي تستغرق دائمًا 5 ثوانٍ لمعالجة 100 عنصر ، و 10 ثوانٍ لمعالجة 200 عنصر وما إلى ذلك ، حيث أن وقت التشغيل يزداد خطيًا مع حجم مجموعة البيانات. إذا استغرقت خوارزمية ثانية 5*5 = 25 ثانية لمعالجة هذه العناصر الـ 200 بدلاً من ذلك ، فقد يتم تصنيفها على أنها O (n^2). لا يوجد "وقت تشغيل ذروة" هنا ، حيث يزداد وقت التشغيل دائمًا عند إلقاء المزيد من البيانات فيه.

في الواقع ، Big O هو الحد الأعلى - لذلك يمكنك القول أن الخوارزمية الأولى كانت O (n^2) أيضًا (إذا كانت n عبارة عن حدود أعلى ، فإن n*n أعلى ، وبالتالي فإن الحد الأعلى ، وإن كان ذلك أكثر مرونة ). يشمل الترميز الشائع للدلالة على الحدود الأخرى ω (أوميغا ، الحد الأدنى) و θ (theta ، الحد الأدنى والأعلى في وقت واحد).

تظهر بعض الخوارزميات (على سبيل المثال ، Quicksort) سلوكًا مختلفًا اعتمادًا على البيانات التي تغذيها - وبالتالي فإن أسوأ حالة هي O (n^2) على الرغم من أنها تتصرف عادة كما لو كانت O (N log n).

Answer 4

هناك فرق كبير بين تلك الأوتار من الكلمات. "أسوأ قضية تشغيل خوارزمية" A "هو بند الاسم ، فهو لا يجعل أي بيان على الإطلاق. "وقت تشغيل الخوارزمية A I IS O (n)" هو جملة ، تخبرنا بشيء عن A.