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

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

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

स्पेस कम्प्लेक्सिटी वर्ग

समय कम्प्लेक्सिटी वर्गों DTIME(f(n)) और NTIME(f(n)) के अनुरूप, कम्प्लेक्सिटी वर्ग DSPACE(f(n)) और 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))$ पूरकता के तहत बंद कर दिया गया है। यह समय और स्थान कम्प्लेक्सिटी वर्गों के बीच एक और गुणात्मक अंतर दिखाता है, क्योंकि गैर-नियतात्मक समय कम्प्लेक्सिटी वर्गों को पूरकता के तहत बंद नहीं माना जाता है; उदाहरण के लिए, यह अनुमान लगाया गया है कि NP ≠ co-NP.।

लॉगस्पेस

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

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

यह वर्ग छद्म यादृच्छिकता और व्युत्पन्नता के क्षेत्र में भी उपयोग देखता है, जहां शोधकर्ता L = RL की खुली समस्या पर विचार करते हैं।

संबंधित गैर-नियतात्मक स्पेस कम्प्लेक्सिटी वर्ग एनएल (कम्प्लेक्सिटी) है।

सहायक स्थान कम्प्लेक्सिटी

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

यह भी देखें

• एल्गोरिदम का विश्लेषण – Study of resources used by an algorithm
• कम्प्यूटेशनल जटिलता सिद्धांत – Inherent difficulty of computational problems
• कम्प्यूटेशनल संसाधन – Something a computer needs needed to solve a problem, such as processing steps or memory