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

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

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

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

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

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

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

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

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

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

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

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

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