ملخص

مراجعة النقاط الرئيسية

تقييم كفاءة الخوارزمية

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

التعقيد الزمني

• يُستخدم التعقيد الزمني لقياس اتجاه زمن تشغيل الخوارزمية مع تزايد حجم البيانات. ويمكنه تقييم كفاءة الخوارزمية بفعالية، لكنه قد يكون أقل إفادة في بعض الحالات، مثل عندما يكون حجم بيانات الإدخال صغيراً أو عندما يتساوى التعقيدان الزمنيان، بحيث يتعذّر المقارنة الدقيقة بين كفاءة الخوارزميتين.
• يُمثَّل التعقيد الزمني في أسوأ حالة بترميز $O$ الكبير، وهو يقابل الحد الأعلى المقارب للدالة، ويعكس مستوى نمو عدد العمليات $T(n)$ عندما يقترب $n$ من اللانهاية الموجبة.
• يتضمن اشتقاق التعقيد الزمني خطوتين: أولاً إحصاء عدد العمليات، ثم تحديد الحد الأعلى المقارب.
• تشمل التعقيدات الزمنية الشائعة، مرتبةً من الأدنى إلى الأعلى: $O(1)$ و$O(\log n)$ و$O(n)$ و$O(n \log n)$ و$O(n^2)$ و$O(2^n)$ و$O(n!)$.
• تعقيد بعض الخوارزميات الزمني غير ثابت، بل يعتمد على توزيع بيانات الإدخال. وينقسم التعقيد الزمني إلى تعقيد أسوأ حالة وتعقيد أفضل حالة وتعقيد الحالة المتوسطة. ويُستخدم تعقيد أفضل حالة نادراً لأن بيانات الإدخال تحتاج عموماً إلى استيفاء شروط صارمة لتحقيق أفضل حالة.
• يعكس التعقيد الزمني المتوسط كفاءة زمن تشغيل الخوارزمية في ظل إدخال بيانات عشوائية، وهو الأقرب إلى أداء الخوارزمية في التطبيقات العملية. ويتطلب حساب التعقيد الزمني المتوسط تحليل توزيع بيانات الإدخال والتوقع الرياضي الناتج عنه.

التعقيد المكاني

• يؤدي التعقيد المكاني غرضاً مشابهاً لغرض التعقيد الزمني، إذ يُستخدم لقياس اتجاه استخدام الخوارزمية للذاكرة مع تزايد حجم البيانات.
• يمكن تقسيم مساحة الذاكرة المرتبطة بتنفيذ الخوارزمية إلى مساحة الإدخال والمساحة المؤقتة ومساحة الإخراج. ولا تُدرَج مساحة الإدخال عادةً في حساب التعقيد المكاني. ويمكن تقسيم المساحة المؤقتة إلى بيانات مؤقتة ومساحة إطار المكدس ومساحة التعليمات، حيث تؤثر مساحة إطار المكدس عادةً في التعقيد المكاني في الدوال التعاودية فقط.
• نهتم عادةً بالتعقيد المكاني في أسوأ حالة فقط، وهو التعقيد المكاني للخوارزمية في ظل أسوأ بيانات إدخال وأسوأ زمن تشغيل.
• تشمل التعقيدات المكانية الشائعة، مرتبةً من الأدنى إلى الأعلى: $O(1)$ و$O(\log n)$ و$O(n)$ و$O(n^2)$ و$O(2^n)$.

أسئلة وأجوبة

س: هل التعقيد المكاني للتعاود الذيل هو $O(1)$؟

نظرياً، يمكن تحسين التعقيد المكاني للدوال ذات التعاود الذيل ليصبح $O(1)$. غير أن معظم لغات البرمجة (مثل Java وPython وC++ وGo وC# وغيرها) لا تدعم التحسين التلقائي للتعاود الذيل، لذا يُعتبر التعقيد المكاني عموماً $O(n)$.

س: ما الفرق بين مصطلحي الدالة والطريقة؟

يمكن تنفيذ الدالة (function) باستقلالية، مع تمرير جميع المعاملات صراحةً. أما الطريقة (method) فهي مرتبطة بكائن، وتُربط ضمناً بالكائن الذي يستدعيها، ويمكنها العمل على البيانات الموجودة في نسخ الفئات.

تستخدم الأمثلة التالية عدة لغات برمجة شائعة للتوضيح.

• لغة C لغة برمجة إجرائية لا تتضمن مفاهيم التوجّه بالكائنات، لذا تحتوي على دوال فقط. غير أنه يمكننا محاكاة البرمجة الكائنية بإنشاء البنى (struct)، وتكون الدوال المرتبطة بالبنى مكافئة للطرق في لغات البرمجة الأخرى.
• لغتا Java وC# لغتا برمجة كائنية التوجه، حيث تكون كتل الشيفرة (الطرق) عادةً جزءاً من فئة. وتتصرف الطرق الساكنة كالدوال لأنها مرتبطة بالفئة ولا تستطيع الوصول إلى متغيرات نسخ معينة.
• تدعم لغتا C++ وPython كلاً من البرمجة الإجرائية (الدوال) والبرمجة الكائنية (الطرق).

س: هل يعكس مخطط «أنواع التعقيد المكاني الشائعة» الحجم المطلق للمساحة المشغولة؟

لا، يعرض المخطط التعقيد المكاني، الذي يعكس اتجاهات النمو لا الحجم المطلق للمساحة المشغولة.

بافتراض $n = 8$، قد تلاحظ أن قيم المنحنيات لا تقابل الدوال. والسبب أن كل منحنى يتضمن حداً ثابتاً يُستخدم لضغط نطاق القيم إلى نطاق مريح بصرياً.

عملياً، لأننا لا نعرف عموماً تكلفة «الحد الثابت» لكل طريقة، لا يمكننا عادةً اختيار الحل الأمثل لحالات مثل $n = 8$ بالاعتماد على التعقيد وحده. لكن بالنسبة إلى $n = 8^5$، يكون الاختيار واضحاً مباشراً، لأن اتجاه النمو هو المتحكم بالفعل.

س: هل توجد حالات تُصمَّم فيها الخوارزميات للتضحية بالزمن (أو المساحة) بناءً على حالات الاستخدام الفعلية؟

في التطبيقات العملية، تختار معظم الحالات التضحية بالمساحة مقابل الزمن. فمثلاً في فهارس قواعد البيانات، نختار عادةً بناء أشجار B+ أو فهارس التجزئة، فنشغل مساحة ذاكرة كبيرة مقابل استعلامات فعّالة بتعقيد $O(\log n)$ أو حتى $O(1)$.

في السيناريوهات التي تكون فيها موارد المساحة ثمينة، قد يُضحّى بالزمن مقابل المساحة. فمثلاً في تطوير الأنظمة المدمجة، تكون ذاكرة الجهاز ثمينة، وقد يتخلى المهندسون عن استخدام جداول التجزئة ويختارون البحث التسلسلي في المصفوفة لتقليل استهلاك الذاكرة، على حساب بحث أبطأ.