contents
- importance of algorithm complexity
- time complexity of an algorithm
- space complexity of an algorithm
أهمية تعقيد الخوارزميات
غالبًا ما توجد أكثر من طريقة واحدة لحل مشكلة معينة باستخدام خوارزميات مختلفة، ونحتاج إلى طريقة لمقارنة هذه الطرق المتعددة. كذلك، هناك مواقف نرغب فيها في معرفة مقدار الوقت والموارد التي قد تستهلكها خوارزمية معينة عند تنفيذها. لقياس أداء الخوارزميات، نستخدم عادةً تحليل تعقيد الزمن والمساحة للخوارزمية. الفكرة هي قياس معدل النمو بناءً على حجم المدخلات. ويكون مستقل عن الجهاز وتكوينه الذي تعمل عليه الخوارزمية، كما يُظهر ارتباطًا مباشرًا بعدد المدخلات، ويمكنه التمييز بين خوارزميتين بوضوح دون أي غموض.
تعقيد الزمن لخوارزمية
تعقيد الزمن لخوارزمية ما يقيس مقدار الوقت الذي تستغرقه الخوارزمية للتنفيذ كدالة لطول المدخلات. لاحظ أن الزمن المستغرق يعتمد على طول المدخلات وليس على وقت التنفيذ الفعلي للجهاز الذي تعمل عليه الخوارزمية. الخوارزمية الصحيحة تأخذ مقدارًا محدودًا من الوقت للتنفيذ. الزمن المطلوب من الخوارزمية لحل مشكلة معينة يُعرف بتعقيد الزمن للخوارزمية، وهو مقياس مهم جدًا في تحليل الخوارزميات. إنه الزمن اللازم لإتمام تنفيذ الخوارزمية. لتقدير تعقيد الزمن، نحتاج إلى النظر في تكلفة كل تعليمة أساسية وعدد المرات التي يتم تنفيذها فيها.
تعقيد المساحة لخوارزمية
يتطلب حل المشكلات باستخدام الكمبيوتر ذاكرة لتخزين البيانات المؤقتة أو النتيجة النهائية أثناء تنفيذ البرنامج. مقدار الذاكرة التي تحتاجها الخوارزمية لحل مشكلة معينة يُعرف بتعقيد المساحة للخوارزمية. يعبر تعقيد المساحة عن مقدار الذاكرة التي تستهلكها الخوارزمية أثناء التشغيل كدالة لحجم المدخلات. لنأخذ مثالًا: لنفترض أن لدينا مشكلة تتعلق بحساب تكرار العناصر في مصفوفة. أي إنه مقدار الذاكرة المطلوبة لإكمال تنفيذ الخوارزمية. لتقدير متطلبات الذاكرة، نحتاج إلى التركيز على جزأين هما جزء ثابت وهو مستقل عن حجم المدخلات. يشمل الذاكرة المخصصة للتعليمات (الكود)، والثوابت، والمتغيرات، وما إلى ذلك، وجزء متغير يعتمد على حجم المدخلات. يشمل الذاكرة المخصصة لمكدس الاستدعاء التكراري والمتغيرات المرجعية وغيرها.
