डेटा संरचना में समय और स्थान की जटिलता

एल्गोरिदम विश्लेषण

एक एल्गोरिथ्म की दक्षता का विश्लेषण दो अलग-अलग चरणों में किया जा सकता है, कार्यान्वयन से पहले और कार्यान्वयन के बाद, जैसा कि

एक प्राथमिक विश्लेषण - इसे एक एल्गोरिथ्म के सैद्धांतिक विश्लेषण के रूप में परिभाषित किया गया है। एल्गोरिथ्म की दक्षता को यह मानकर मापा जाता है कि अन्य सभी कारक उदा। प्रोसेसर की गति स्थिर होती है और कार्यान्वयन पर इसका कोई प्रभाव नहीं पड़ता है।

एक पश्च विश्लेषण - इसे एक एल्गोरिथ्म के अनुभवजन्य विश्लेषण के रूप में परिभाषित किया गया है। चयनित एल्गोरिथम प्रोग्रामिंग भाषा का उपयोग करके कार्यान्वित किया जाता है। अगला चयनित एल्गोरिथम लक्ष्य कंप्यूटर मशीन पर क्रियान्वित किया जाता है। इस विश्लेषण में, चलने का समय और आवश्यक स्थान जैसे वास्तविक आँकड़े एकत्र किए जाते हैं।

एल्गोरिथम विश्लेषण में शामिल विभिन्न कार्यों के निष्पादन या चलने के समय से निपटा जाता है। किसी ऑपरेशन के रनिंग टाइम को प्रति ऑपरेशन निष्पादित कंप्यूटर निर्देशों की संख्या के रूप में परिभाषित किया जा सकता है।

एल्गोरिदम जटिलता

मान लीजिए X को एल्गोरिथम के रूप में माना जाता है और N को इनपुट डेटा के आकार के रूप में माना जाता है, एल्गोरिथम X द्वारा लागू किया गया समय और स्थान दो मुख्य कारक हैं जो X की दक्षता निर्धारित करते हैं।

समय कारक - समय की गणना या मापन प्रमुख कार्यों की संख्या की गणना करके किया जाता है जैसे कि सॉर्टिंग एल्गोरिदम में तुलना।

स्पेस फैक्टर - एल्गोरिथ्म द्वारा आवश्यक अधिकतम मेमोरी स्पेस की गणना करके स्पेस की गणना या मापन किया जाता है।

एल्गोरिदम f(N) की जटिलता इनपुट डेटा के आकार के रूप में N के संबंध में एल्गोरिथम द्वारा आवश्यक रनिंग टाइम और/या स्टोरेज स्पेस प्रदान करती है।

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

एल्गोरिथम की अंतरिक्ष जटिलता अपने जीवन चक्र में एल्गोरिथम के लिए आवश्यक मेमोरी स्पेस की मात्रा का प्रतिनिधित्व करती है।

एल्गोरिथम के लिए आवश्यक स्थान निम्नलिखित दो घटकों के योग के बराबर होता है

एक निश्चित भाग जो कुछ डेटा और चर (यानी साधारण चर और स्थिरांक, प्रोग्राम आकार आदि) को संग्रहीत करने के लिए आवश्यक स्थान है, जो समस्या के आकार पर निर्भर नहीं हैं।

एक चर भाग चर के लिए आवश्यक एक स्थान है, जिसका आकार पूरी तरह से समस्या के आकार पर निर्भर है। उदाहरण के लिए, रिकर्सन स्टैक स्पेस, डायनामिक मेमोरी आवंटन इत्यादि।

किसी भी एल्गोरिथम की अंतरिक्ष जटिलता एस (पी) एस (पी) =ए + एसपी (आई) है जहां ए को निश्चित भाग के रूप में माना जाता है और एस (आई) को एल्गोरिथम के चर भाग के रूप में माना जाता है जो कि उदाहरण की विशेषता पर निर्भर करता है I . निम्नलिखित एक सरल उदाहरण है जो अवधारणा को समझाने की कोशिश करता है

एल्गोरिदम

SUM(P, Q)
Step 1 - START
Step 2 - R ← P + Q + 10
Step 3 - Stop

यहां हमारे पास तीन चर P, Q और R और एक स्थिरांक है। इसलिए एस (पी) =1+3। अब स्पेस दिए गए निरंतर प्रकार और चर के डेटा प्रकारों पर निर्भर है और इसे तदनुसार गुणा किया जाएगा।

समय की जटिलता

एक एल्गोरिथ्म की समय जटिलता एल्गोरिथ्म द्वारा पूरा होने तक निष्पादित करने के लिए आवश्यक समय की मात्रा का प्रतिनिधित्व है। समय की आवश्यकताओं को एक संख्यात्मक फ़ंक्शन t(N) के रूप में निरूपित या परिभाषित किया जा सकता है, जहां t(N) को चरणों की संख्या के रूप में मापा जा सकता है, बशर्ते प्रत्येक चरण में निरंतर समय लगे।

उदाहरण के लिए, दो n-बिट पूर्णांकों के योग के मामले में, N कदम उठाए जाते हैं। नतीजतन, कुल कम्प्यूटेशनल समय t(N) =c*n है, जहां c दो बिट्स को जोड़ने के लिए लिया गया समय है। यहाँ, हम देखते हैं कि t(N) इनपुट आकार बढ़ने पर रैखिक रूप से बढ़ता है।