أفضل حالة وأسوأ حالة والحالة المتوسطة
ثلاث طرق لقياس خوارزمية
تعتمد تكلفة كل خوارزمية على مدخلاتها. يمكن لمدخلين من نفس الحجم أن ينتجا أوقات تشغيل مختلفة جداً. يصيغ تحليل التعقيد بشكل رسمي ثلاث وجهات نظر حول هذا الاختلاف.
أفضل حالة — Ω (Omega): المدخل الذي يجعل الخوارزمية تنتهي بأسرع وقت. للبحث الخطي على قائمة من N عناصر: Ω(1) — الهدف يحتل الموضع الأول. مقارنة واحدة، انتهى.
أسوأ حالة — O (Big O): المدخل الذي يجعل الخوارزمية تنتهي ببطء. للبحث الخطي: O(N) — الهدف يقع في نهاية القائمة، أو لا يظهر على الإطلاق. كل عنصر يتطلب فحصاً.
الحالة المتوسطة — Θ (Theta): التكلفة المتوقعة عبر جميع المدخلات الممكنة، بافتراض التوزيع المنتظم. للبحث الخطي حيث يكون الهدف محتملاً بالتساوي أن يحتل أي من مواضع N: Θ(N/2) = Θ(N). الثابت 1/2 ينخفض لأن Theta تعبر عن النمو المقارب الضيق، وليس المعاملات الدقيقة.
لماذا تهيمن أسوأ حالة
يجب أن تتعامل الأنظمة مع أسوأ حالة. استعلام قاعدة بيانات يتوسط 10 ميلي ثانية لكنه يستغرق أحياناً 60 ثانية ينتج فشلاً مرئياً للمستخدم. يصمم المهندسون حدود أسوأ حالة بحيث يظل الأداء متنبأ به بغض النظر عن المدخل. يحمل تحليل الحالة المتوسطة قيمة في الإعدادات الاحتمالية، لكن تحليل أسوأ حالة يعطي ضمانات.
تحليل حالات البحث الثنائي
يعمل البحث الثنائي فقط على المصفوفات المرتبة. في كل خطوة: قارن الهدف بالعنصر في نقطة المنتصف. إذا كان الهدف مساوياً لنقطة المنتصف، أرجعه. إذا كان الهدف أصغر، كرر على النصف الأيسر. إذا كان أكبر، كرر على النصف الأيمن.
كل مقارنة تزيل نصف المرشحين المتبقيين.
نمو الذاكرة و المقابلات الوقت-الفضاء
حساب الذاكرة، ليس العمليات
يقيس تعقيد الوقت عدد العمليات التي تنفذها خوارزمية. يقيس تعقيد الفضاء الذاكرة الإضافية التي تخصصها بعد مدخلاتها. كلاهما مهم في الأنظمة الإنتاجية: خوارزمية سريعة التي تخصص ذاكرة O(N²) ستستنزف خادماً.
فضاء O(1): ذاكرة إضافية ثابتة بغض النظر عن N. ترتيب في مكانه (مثل ترتيب الإدراج) يبدل العناصر داخل المصفوفة الأصلية. يستخدم حفنة من المتغيرات المؤقتة — O(1) بغض النظر عن حجم المصفوفة.
فضاء O(N): ذاكرة تتناسب مع حجم المدخل. إنشاء نسخة من مصفوفة N عنصر يتطلب N فتحات. بناء مجموعة هاش من قائمة N سلسلة يخزن حتى N عناصر.
فضاء O(N²): ذاكرة تتناسب مع N². بناء مصفوفة المجاورة N×N لرسم بياني مع N رؤوس يتطلب N² خانات. عند N = 10,000 رؤوس، هذا هو 10^8 مدخلات — مئات الميجابايتات لشبكة بوليان بسيطة.
مقابلات الوقت-الفضاء
واحد من الحركات الأساسية في تصميم الخوارزميات: تبديل الفضاء مقابل الوقت، أو الوقت مقابل الفضاء.
جداول الهاش تستخدم فضاء إضافي O(N) لتحقيق بحث O(1). بدون جدول الهاش، مسح على قائمة يحقق بحث O(N) مع فضاء إضافي O(1). جدول الهاش يدفع الذاكرة لشراء السرعة.
التذكر يخزن النتائج المحسوبة سابقاً (فضاء O(N) أو أكثر) لتجنب إعادة حسابها. فيبوناتشي العودية بدون تذكر تعمل في وقت O(2^N). مع التذكر: O(N) وقت و O(N) فضاء. استثمار الفضاء يقلل الوقت بشكل أسي.
قاموس الهاش مقابل القائمة المرتبة
قارن استراتيجيتين لعد حدوث الكلمات في وثيقة من N كلمات:
الاستراتيجية أ: قاموس (خريطة الهاش). أدرج كل كلمة؛ زيادة عددها.
الاستراتيجية ب: احتفظ بقائمة مرتبة من الكلمات المرئية؛ استخدم البحث الثنائي للتحقق من العضوية قبل الإدراج.
التحليل المطفأ: توزيع التكلفة
عندما لا تضر النفقات العرضية الأداء المتوسطة
بعض العمليات تكون عرضية باهظة لكن رخيصة في المتوسط عبر سلسلة. يحسب التحليل المطفأ تكلفة المتوسط لكل عملية عبر السلسلة الكاملة — وليس تكلفة أسوأ حالة لعملية واحدة.
مصفوفة ديناميكية (قائمة Python، ArrayList Java): تبدأ بقدرة 1. عندما تكون ممتلئة، تضاعف القدرة. المضاعفة تنسخ جميع العناصر الموجودة: عمل O(N) لإضافة واحدة. لكن المضاعفات نادرة. بعد N إضافة إجمالية، كم عدد عمليات النسخ الإجمالية التي حدثت؟
تحدث المضاعفات بأحجام 1, 2, 4, 8, ..., N/2. عدد النسخ: 1 + 2 + 4 + ... + N/2. هذه سلسلة هندسية تجمع إلى N − 1 نسخ إجمالي عبر كل N إضافة. متوسط النسخ لكل إضافة: (N − 1) / N < 1، إذاً O(1) مطفأة لكل إضافة رغم تكلفة O(N) أسوأ حالة لكل مضاعفة.
لماذا يهم التحليل المطفأ
نظام يتوقف أحياناً لتغيير الحجم أو إعادة التوازن أو دمج بنية قد يبدو أن لديه عمليات فردية مزعجة أسوأ حالة. يكشف التحليل المطفأ أن الإنذار خاطئ: الأحداث العرضية المكلفة تُدفع من قبل الكثير من الأحداث الرخيصة. فهم التكلفة المطفأة يمنع الهندسة المفرطة: إضافة تعقيد لتجنب عملية عرضية O(N) التي تساهم فقط O(1) مطفأة هي عمل مهدر.
للذهاب أعمق: تطبق دورة الاختيار (unhamming) تحليل التعقيد على الخلل الحقيقي في البرامج الإنتاجية. انظر الفصل المفقود: التعقيد الخوارزمي & MOAD-0001: الخلل الرسوبي.
إدراج جدول الهاش المطفأ
جدول هاش يبدأ فارغاً ويضاعف القدرة كلما تجاوز معامل التحميل 0.75. إدراج 1,000 عنصر يشغل بالضبط 10 مضاعفات بقدرات 1, 2, 4, 8, 16, 32, 64, 128, 256, 512.