كفاءة خوارزمية

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

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

نظرة عامة

تعتبر الخوارزمية ذات كفاءة إذا كان استخدامها للموارد أقل من "المستوى المقبول"، ويمكن القول أن المستوى المقبول يعني أن الخوارزمية سوف تستهلك كمّا معقولاً من الموارد. منذ 1950، شهدت الحواسيب تطورًا كبيرًا بالنسبة لكل من الطاقة الحاسوبية المتاحة وكمية الذاكرة المتاحة، لذلك فإن مستويات القبول الحالية لا يمكن مقارنتها مع المستويات المقبولة قبل 10 سنوات مثلاً.

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

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

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

التحليل النظري

يمكن تحليل الخوارزمية نظريًا من خلال حساب تعقيد الخوارزمية باستخدام رمز O الكبير، حيث يرمز إلى مدى تعقيد الخوارزمية كاقتران مرتبط بحجم البيانات.

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

مقياس استخدام الموارد

يُعّبر عادةً عن المقياس من خلال اقتران مرتبط بحجم البيانات n

أكثر مِقياسّين يُعتمد عليهما هما:

1. الزمن: مقدار الزمن الذي تستغرقه الخوارزمية لتنهي عملها.

2. المساحة: كمية الذاكرة (تحديداً الذاكرة العشوائية) التي تحتاجها الخوارزمية. والمساحة تُقسم إلى قسمين: حجم المساحة التي تحتاجها الشيفرة المصدرية للخوارزمية وحجم البيانات التي تعالجها الشيفرة.

الزمن

نظريًا

يُستخدم التعقيد الزمني لتحليل الوقت الذي تستخدمه الخوارزمية بالنسبة لكمية المدخلات.

النتيجة يمكن التعبير عنها بواسطة  رمز O الكبير. يمكن من خلال هذه العملية مقارنة الخوارزميات خاصة إذا كان لدينا كم كبير من البيانات لمعالجتها.

المساحة

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

هناك أربع جوانب لاستخدام الذاكرة يجب التنبه لها:

1. حجم الذاكرة التي تحتاجها الشيفرة البرمجية للخوارزمية
2. حجم الذاكرة للبيانات المُدخلة
3. حجم الذاكرة للبيانات المخرجة (بعض الخوارزميات مثل خوارزميات الترتيب لا تحتاج إلى مخرجات)
4. حجم الذاكرة التي تحتاجها الخوارزمية للحسابات أثناء عملها.

الحواسيب الحالية تمتلك مساحة كبيرة من الذاكرة، لذلك تقليص حجم الخوارزمية ليتناسب مع حجم الذاكرة لم يعد مشكلة كبيرة نواجهها. لكن مع وجود ثلاث أنواع من الذاكرة فالأمر مختلف قليلاً:

1. الذاكرة المخبئية Cache Memory – وهذه تعمل بسرعة عالية جداً متناسبة مع وحدة المعالجة المركزية.
2. الذاكرة الفيزيائية الرئيسة، وهذه تعمل بسرعة أقل من سرعة وحدة المعالجة المركزية CPU..
3. الذاكرة الافتراضية – وهذه توحي للمستخدم بأن هناك مساحة كبيرة من الذاكرة، لكن أبطأ بآلاف المرات من الذاكرة العشوائية.

الخوارزمية التي تحتاج ذاكرة تتناسب مع مساحة الذاكرة المخبئية Cache Memory سيكون أداؤها أفضل بمراحل من الخوارزمية التي تحتاج إلى سعة الذاكرة الرئيسة، وبدورها ستكون أسرع بكثير من الخوارزمية التي تحتاج إلى الذاكرة الافتراضية.