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

एल्गोरिदम विश्लेषण (Algorithm Analysis)

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

ए प्रायोरी विश्लेषण (A Priori Analysis) - यह एल्गोरिदम का सैद्धांतिक विश्लेषण है। एल्गोरिदम की दक्षता को यह मानकर मापा जाता है कि अन्य सभी कारक जैसे प्रोसेसर की गति, स्थिर हैं और कार्यान्वयन पर कोई प्रभाव नहीं डालते।

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

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

एल्गोरिदम जटिलता (Algorithm Complexity)

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

समय कारक (Time Factor) - समय की गणना या माप कुंजी ऑपरेशन्स की संख्या गिनकर की जाती है जैसे सॉर्टिंग एल्गोरिदम में तुलनाएँ (Comparisons)।

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

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

स्थान जटिलता (Space Complexity)

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

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

• एक निश्चित भाग (Fixed Part) जो कुछ डेटा और वेरिएबल्स को स्टोर करने के लिए आवश्यक स्थान है (यानी साधारण वेरिएबल्स और कॉन्स्टेंट्स, प्रोग्राम साइज़ आदि), जो समस्या के आकार पर निर्भर नहीं करते।
• एक परिवर्तनीय भाग (Variable Part) जो उन वेरिएबल्स द्वारा आवश्यक स्थान है जिनका आकार पूरी तरह से समस्या के आकार पर निर्भर करता है। उदाहरण के लिए, रिकर्सन स्टैक स्पेस, डायनामिक मेमोरी एलोकेशन आदि।

किसी भी एल्गोरिदम p की स्थान जटिलता S(p) है: S(p) = A + Sp(I) जहां A निश्चित भाग है और S(I) एल्गोरिदम का परिवर्तनीय भाग है जो इंस्टेंस विशेषता I पर निर्भर करता है। निम्न एक सरल उदाहरण है जो अवधारणा को समझाने का प्रयास करता है:

एल्गोरिदम

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

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

समय जटिलता (Time Complexity)

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

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