أسوأ حالة تعقيد

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

في حالة وقت التشغيل، يشير تعقيد الوقت في أسوأ الحالات إلى أطول وقت تشغيل يتم تنفيذه بواسطة خوارزمية مع مراعاة أي إدخال بحجم n ، وبالتالي يضمن أن الخوارزمية ستنتهي في الفترة الزمنية المشار إليها. يُستخدم ترتيب النمو (على سبيل المثال الخطي أو اللوغاريتمي ) لتعقيد أسوأ الحالات عادةً لمقارنة كفاءة خوارزميتين.

يجب مقارنة أسوأ حالة تعقيد لخوارزمية ما مع متوسط ​​​​تعقيدها ، وهو مقياس متوسط ​​​​لكمية الموارد التي تستخدمها الخوارزمية على إدخال عشوائي.

بالنظر إلى نموذج حسابي وخوارزمية تتوقف عند كل إدخال ، فإن التعيين يسمى تعقيد الوقت إذا ، لكل سلسلة إدخال ، يتوقف بعد خطوات بالضبط. ${\displaystyle {\mathsf {أ}}}$${\displaystyle s}$${\displaystyle t_{\mathsf {A}}\colon \{0,1\}^{\star }\to \mathbb {N} }$${\displaystyle {\mathsf {أ}}}$ ${\displaystyle s}$${\displaystyle {\mathsf {أ}}}$${\displaystyle t_{\mathsf {A}}(s)}$

نظرًا لأننا مهتمون عادةً باعتماد تعقيد الوقت على أطوال إدخال مختلفة، وإساءة استخدام المصطلحات، يُشار أحيانًا إلى تعقيد الوقت باسم التعيين ، والذي يتم تحديده من خلال أقصى تعقيد ${\displaystyle t_{\mathsf {A}}\colon \mathbb {N} \to \mathbb {N} }$

${\displaystyle t_{\mathsf {A}}(n):=\max _{s\in \{0,1\}^{n}}t_{\mathsf {A}}(s)}$

من المدخلات ذات الطول أو الحجم . ${\displaystyle s}$${\displaystyle \leq n}$

يمكن تقديم تعريفات مماثلة لتعقيد الفضاء ، وتعقيد العشوائية، وما إلى ذلك.

في كثير من الأحيان، يتم إعطاء تعقيد الخوارزمية في تدوين Big-O المقارب ، والذي يعطي معدل نموها في شكل دالة مقارنة ذات قيمة حقيقية معينة والمعنى: ${\displaystyle t_{\mathsf {أ}}}$${\displaystyle {\mathsf {أ}}}$${\displaystyle t_{\mathsf {A}}=O(g(n))}$${\displaystyle g(n)}$

• يوجد عدد حقيقي موجب وعدد طبيعي بحيث${\displaystyle M}$ ${\displaystyle n_{0}}$

${\displaystyle |t_{\mathsf {A}}(n)|\leq Mg(n)\quad {\text{ لجميع }}n\geq n_{0}.}$

في كثير من الأحيان، تكون الصياغة على النحو التالي:

• "الخوارزمية لها أسوأ حالة تعقيد ."${\displaystyle {\mathsf {أ}}}$${\displaystyle O(g(n))}$

أو حتى فقط:

• "الخوارزمية لها تعقيد ."${\displaystyle {\mathsf {أ}}}$${\displaystyle O(g(n))}$

فكر في إجراء فرز بالإدراج على أرقام على جهاز وصول عشوائي . أفضل حالة للخوارزمية هي عندما يتم فرز الأرقام بالفعل، والتي تتخذ خطوات لأداء المهمة. ومع ذلك، فإن الإدخال في أسوأ حالة للخوارزمية هو عندما يتم فرز الأرقام عكسيًا وتتخذ خطوات لفرزها؛ وبالتالي فإن أسوأ تعقيد زمني للفرز بالإدراج هو . ${\displaystyle n}$${\displaystyle O(n)}$${\displaystyle O(n^{2})}$${\displaystyle O(n^{2})}$

• تحليل الخوارزميات

• توماس إتش. كورمن ، تشارلز إي. ليسيرسون ، رونالد إل. ريفيست ، وكليفورد شتاين . مقدمة في الخوارزميات ، الطبعة الثانية. مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل، 2001. رقم ISBN  0-262-03293-7 . الفصل 2.2: تحليل الخوارزميات، ص 25-27.
• أوديد جولدريتش. التعقيد الحسابي: منظور مفاهيمي. مطبعة جامعة كامبريدج، 2008. ISBN 0-521-88473-X ، ص. 32.