تعقيد المساحة

يُعرَّف تعقيد المساحة للخوارزمية أو بنية البيانات بأنه مقدار مساحة الذاكرة اللازمة لحل مسألة حسابية معينة ، وذلك تبعًا لخصائص المدخلات. وهو الذاكرة التي تحتاجها الخوارزمية حتى اكتمال تنفيذها. ^{[ 1 ]} ويشمل ذلك مساحة الذاكرة المستخدمة من قِبل المدخلات، والتي تُسمى مساحة المدخلات ، وأي ذاكرة أخرى (مساعدة) تستخدمها الخوارزمية أثناء التنفيذ، والتي تُسمى المساحة المساعدة .

على غرار تعقيد الوقت ، غالبًا ما يُعبَّر عن تعقيد المساحة تقاربياً باستخدام ترميز Big O ، مثل:${\displaystyle O(n),}$${\displaystyle O(n\log n),}$${\displaystyle O(n^{\alpha }),}$${\displaystyle O(2^{n}),}$إلخ، حيث n هي خاصية من خصائص المدخلات التي تؤثر على تعقيد المساحة.

على غرار فئتي التعقيد الزمني DTIME(f(n)) و NTIME(f(n)) ، فإن فئتي التعقيد DSPACE(f(n)) و NSPACE(f(n)) هما مجموعتا اللغات التي يمكن تحديدها بواسطة آلات تورينج الحتمية (على التوالي، غير الحتمية) التي تستخدم${\displaystyle O(f(n))}$الفضاء. تسمح فئات التعقيد PSPACE و NPSPACE${\displaystyle f}$أن تكون أي متعددة حدود، على غرار P و NP . أي، $${\displaystyle {\mathsf {PSPACE}}=\bigcup _{c\in \mathbb {Z} ^{+}}{\mathsf {DSPACE}}(n^{c})}$$ و $${\displaystyle {\mathsf {NPSPACE}}=\bigcup _{c\in \mathbb {Z} ^{+}}{\mathsf {NSPACE}}(n^{c})}$$

تنص نظرية التسلسل الهرمي للفضاء على أنه بالنسبة لجميع الدوال القابلة للإنشاء في الفضاء${\displaystyle f(n),}$توجد مشكلة يمكن حلها بواسطة آلة ذات${\displaystyle f(n)}$مساحة الذاكرة، ولكن لا يمكن حلها بواسطة جهاز ذي مساحة ذاكرة أقل من${\displaystyle f(n)}$فضاء.

تتحقق القيود التالية بين فئات التعقيد. ^{[ 2 ]}$${\displaystyle {\mathsf {DTIME}}(f(n))\subseteq {\mathsf {DSPACE}}(f(n))\subseteq {\mathsf {NSPACE}}(f(n))\subseteq {\mathsf {DTIME}}\left(2^{O(f(n))}\right)}$$

علاوة على ذلك، تنص نظرية سافيتش على الاحتواء العكسي الذي إذا${\displaystyle f\in \Omega (\log(n)),}$$${\displaystyle {\mathsf {NSPACE}}(f(n))\subseteq {\mathsf {DSPACE}}\left((f(n))^{2}\right).}$$

وكنتيجة مباشرة لذلك،${\displaystyle {\mathsf {PSPACE}}={\mathsf {NPSPACE}}.}$تُعدّ هذه النتيجة مفاجئة لأنها تُشير إلى أن عدم الحتمية يُمكن أن يُقلّل المساحة اللازمة لحلّ مشكلة ما بمقدار ضئيل فقط. في المقابل، تفترض فرضية الزمن الأسي أنه بالنسبة لتعقيد الوقت، يُمكن أن تكون هناك فجوة أسية بين التعقيد الحتمي وغير الحتمي.

تنص نظرية Immerman -Szelepcsényi على ذلك مرة أخرى${\displaystyle f\in \Omega (\log(n)),}$${\displaystyle {\mathsf {NSPACE}}(f(n))}$تُعتبر فئة NP مغلقة تحت عملية الإكمال. وهذا يُظهر فرقًا نوعيًا آخر بين فئات التعقيد الزمني والمكاني، إذ لا يُعتقد أن فئات التعقيد الزمني غير الحتمية مغلقة تحت عملية الإكمال؛ على سبيل المثال، يُفترض أن NP ≠ co-NP . ^{[ 3 ] [ 4 ]}

L أو LOGSPACE هي مجموعة المسائل التي يمكن حلها بواسطة آلة تورينج حتمية باستخدام فقط${\displaystyle O(\log n)}$مساحة الذاكرة فيما يتعلق بحجم المدخلات. حتى عداد واحد يمكنه فهرسة كامل${\displaystyle n}$يتطلب إدخال بت واحد${\displaystyle \log n}$المساحة، لذلك لا تستطيع خوارزميات LOGSPACE الاحتفاظ إلا بعدد ثابت من العدادات أو المتغيرات الأخرى ذات التعقيد البتّي المماثل.

تُعدّ خوارزميات LOGSPACE وغيرها من الخوارزميات ذات التعقيد المكاني شبه الخطي مفيدةً عند معالجة البيانات الضخمة التي لا تتسع لها ذاكرة الوصول العشوائي (RAM) للحاسوب . وهي مرتبطة بخوارزميات التدفق ، لكنها تُقيّد فقط مقدار الذاكرة المُتاحة، بينما تفرض خوارزميات التدفق قيودًا إضافية على كيفية إدخال البيانات إليها. كما تُستخدم هذه الخوارزميات في مجال العشوائية الزائفة وإزالة العشوائية ، حيث يدرس الباحثون مسألة ما إذا كان L = RL . ^{[ 5 ] [ 6 ]}

فئة تعقيد المساحة غير الحتمية المقابلة هي NL .

على المدىيشير مصطلح "المساحة الإضافية" إلى المساحة التي لا تشغلها المدخلات. يمكن تعريف تعقيد المساحة الإضافية رسميًا باستخدامآلة تورينجبشريط إدخالمنفصللا يمكن الكتابة إليه، بل القراءة فقط، وشريط عمل تقليدي يمكن الكتابة إليه. ثم يُعرَّف تعقيد المساحة الإضافية (ويُحلَّل) من خلال شريط العمل. على سبيل المثال، لنأخذ في الاعتبارالبحث العميق أولًافيشجرة ثنائية متوازنةمع${\displaystyle n}$العقد: تعقيد المساحة المساعدة لها هو${\displaystyle \Theta (\log n).}$

• تحليل الخوارزميات – دراسة الموارد التي تستخدمها الخوارزمية 
• نظرية التعقيد الحسابي – الصعوبة الكامنة في المسائل الحسابية 
• الموارد الحاسوبية – جانب من جوانب نظرية التعقيد الحسابي 
• التعقيد الزمني – تقدير الوقت المستغرق لتشغيل خوارزمية