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

أسس التعقيد الفضائي

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

العوامل التي تؤثر على استخدام الفضاء

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

حساب التعقيد الفضائي

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

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