स्पेस कम्प्लेक्सिटी

एक कलन विधि या कंप्यूटर प्रोग्राम की स्पेस जटिलता इनपुट की विशेषताओं के एक फ़ंक्शन के रूप में कम्प्यूटेशनल समस्या के एक उदाहरण को हल करने के लिए आवश्यक मेमोरी स्पेस की मात्रा है। यह एक एल्गोरिदम द्वारा पूरी तरह से निष्पादित होने तक आवश्यक मेमोरी है। इसमें इसके इनपुट द्वारा उपयोग की जाने वाली मेमोरी स्पेस, जिसे इनपुट स्पेस कहा जाता है, और निष्पादन के दौरान उपयोग की जाने वाली कोई अन्य (सहायक) मेमोरी शामिल है, जिसे सहायक स्पेस कहा जाता है।

समय जटिलता के समान, अंतरिक्ष जटिलता को अक्सर बड़ा ओ अंकन में स्पर्शोन्मुख रूप से व्यक्त किया जाता है, जैसे कि $O(n),$ $O(n\log n),$ $O(n^{\alpha }),$ $O(2^{n}),$ आदि, कहाँ n अंतरिक्ष जटिलता को प्रभावित करने वाले इनपुट की एक विशेषता है।

अंतरिक्ष जटिलता वर्ग

समय जटिलता वर्गों DTIME|DTIME(f(n)) और NTIME|NTIME(f(n)) के अनुरूप, जटिलता वर्ग DSPACE|DSPACE(f(n)) और NSPACE|NSPACE(f(n)) सेट हैं ऐसी भाषाएँ जो नियतात्मक (क्रमशः, गैर-नियतात्मक) ट्यूरिंग मशीनों द्वारा निर्णय लेने योग्य हैं जो उपयोग करती हैं $O(f(n))$ अंतरिक्ष। जटिलता वर्ग PSPACE और NPSPACE अनुमति देते हैं $f$ पी (जटिलता) और एनपी (जटिलता) के अनुरूप, कोई भी बहुपद होना। वह है,

$${\mathsf {PSPACE}}=\bigcup _{c\in \mathbb {Z} ^{+}}{\mathsf {DSPACE}}(n^{c})$$

और

$${\mathsf {NPSPACE}}=\bigcup _{c\in \mathbb {Z} ^{+}}{\mathsf {NSPACE}}(n^{c})$$

वर्गों के बीच संबंध

अंतरिक्ष पदानुक्रम प्रमेय बताता है कि, सभी अंतरिक्ष-निर्माण योग्य कार्यों के लिए $f(n),$ वहाँ एक समस्या मौजूद है जिसे एक मशीन द्वारा हल किया जा सकता है $f(n)$ मेमोरी स्पेस, लेकिन एसिंप्टोटिकली कम वाली मशीन द्वारा हल नहीं किया जा सकता है $f(n)$ अंतरिक्ष।

जटिलता वर्गों के बीच निम्नलिखित नियंत्रण कायम हैं।

$${\mathsf {DTIME}}(f(n))\subseteq {\mathsf {DSPACE}}(f(n))\subseteq {\mathsf {NSPACE}}(f(n))\subseteq {\mathsf {DTIME}}\left(2^{O(f(n))}\right)$$

इसके अलावा, सैविच का प्रमेय विपरीत रोकथाम देता है कि यदि $f\in \Omega (\log(n)),$

$${\mathsf {NSPACE}}(f(n))\subseteq {\mathsf {DSPACE}}\left((f(n))^{2}\right).$$

प्रत्यक्ष परिणाम के रूप में, ${\mathsf {PSPACE}}={\mathsf {NPSPACE}}.$ यह परिणाम आश्चर्यजनक है क्योंकि यह बताता है कि गैर-नियतिवाद किसी समस्या को हल करने के लिए आवश्यक स्थान को केवल थोड़ी मात्रा में कम कर सकता है। इसके विपरीत, घातीय समय परिकल्पना का अनुमान है कि समय जटिलता के लिए, नियतात्मक और गैर-नियतात्मक जटिलता के बीच एक घातीय अंतर हो सकता है।

इमरमैन-स्ज़ेलेपेसेनी प्रमेय कहता है कि, फिर से $f\in \Omega (\log(n)),$ ${\mathsf {NSPACE}}(f(n))$ पूरकता के तहत बंद कर दिया गया है। यह समय और स्थान जटिलता वर्गों के बीच एक और गुणात्मक अंतर दिखाता है, क्योंकि गैर-नियतात्मक समय जटिलता वर्गों को पूरकता के तहत बंद नहीं माना जाता है; उदाहरण के लिए, यह अनुमान लगाया गया है कि एनपी ≠ सह-एनपी।

लॉगस्पेस

एल (जटिलता) या लॉगस्पेस समस्याओं का समूह है जिसे केवल नियतात्मक ट्यूरिंग मशीन द्वारा हल किया जा सकता है $O(\log n)$ इनपुट आकार के संबंध में मेमोरी स्पेस। यहां तक ​​कि एक भी काउंटर जो संपूर्ण को अनुक्रमित कर सकता है $n$-बिट इनपुट की आवश्यकता है $\log n$ स्थान, इसलिए LOGSPACE एल्गोरिदम केवल काउंटरों की एक स्थिर संख्या या समान बिट जटिलता के अन्य चर बनाए रख सकता है।

लॉगस्पेस और अन्य सब-लीनियर स्पेस जटिलता बड़े डेटा को संसाधित करते समय उपयोगी होती है जो कंप्यूटर की रैंडम एक्सेस मेमोरी में फिट नहीं हो सकती है। वे स्ट्रीमिंग एल्गोरिदम से संबंधित हैं, लेकिन केवल यह सीमित करते हैं कि कितनी मेमोरी का उपयोग किया जा सकता है, जबकि स्ट्रीमिंग एल्गोरिदम में एल्गोरिदम में इनपुट को कैसे फीड किया जाता है, इस पर और भी बाधाएं हैं। यह वर्ग छद्म यादृच्छिकता और व्युत्पन्नता के क्षेत्र में भी उपयोग देखता है, जहां शोधकर्ता एल (जटिलता) = आरएल (जटिलता) की खुली समस्या पर विचार करते हैं। संबंधित गैर-नियतात्मक अंतरिक्ष जटिलता वर्ग एनएल (जटिलता) है।

सहायक स्थान जटिलता

शब्दauxiliary space इनपुट द्वारा उपभोग किए गए स्थान के अलावा अन्य स्थान को संदर्भित करता है। सहायक अंतरिक्ष जटिलता को औपचारिक रूप से एक ट्यूरिंग मशीन के संदर्भ में परिभाषित किया जा सकता है जिसमें एक अलग इनपुट टेप होता है जिसे लिखा नहीं जा सकता, केवल पढ़ा जा सकता है, और एक पारंपरिक कामकाजी टेप जिसे लिखा जा सकता है। फिर सहायक स्थान जटिलता को कार्यशील टेप के माध्यम से परिभाषित (और विश्लेषण) किया जाता है। उदाहरण के लिए, बाइनरी ट्री की गहराई-पहली खोज पर विचार करें#बाइनरी ट्री के प्रकार $n$ नोड्स: इसकी सहायक स्थान जटिलता है $\Theta (\log n).$

यह भी देखें

• Analysis of algorithms
• Computational complexity theory
• Computational resource