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

في تصميم الخوارزميات، نسعى إلى تحقيق المستويين التاليين من الأهداف بالترتيب.

1. إيجاد حل للمسألة: يجب أن تحصل الخوارزمية على الحل الصحيح بموثوقية ضمن نطاق الإدخال المحدد.
2. السعي إلى الحل الأمثل: قد توجد حلول متعددة للمسألة نفسها، ونأمل في إيجاد خوارزمية تكون فعّالة قدر الإمكان.

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

• الكفاءة الزمنية: طول المدة التي تستغرقها الخوارزمية في التشغيل.
• الكفاءة المكانية: حجم مساحة الذاكرة التي تشغلها الخوارزمية.

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

تنقسم طرق تقييم الكفاءة أساساً إلى نوعين: الاختبار الفعلي والتقدير النظري.

الاختبار الفعلي

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

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

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

التقدير النظري

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

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

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

يتغلب تحليل التعقيد على عيوب طريقة الاختبار الفعلي، ويتجلى ذلك في الجوانب التالية.

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

يوفر لنا تحليل التعقيد "مسطرة" لتقييم كفاءة الخوارزميات، تتيح لنا قياس موارد الزمن والمساحة اللازمة لتنفيذ خوارزمية معينة ومقارنة الكفاءة بين الخوارزميات المختلفة.

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

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