एसिम्प्टोटिक एनालिसिस
एसिम्प्टोटिक विश्लेषण का उपयोग करके, हम इनपुट आकार के आधार पर एल्गोरिदम के प्रदर्शन के बारे में एक विचार प्राप्त कर सकते हैं। हमें सटीक रनिंग टाइम की गणना नहीं करनी चाहिए, बल्कि रनिंग टाइम और इनपुट आकार के बीच संबंध ढूंढना चाहिए। हमें रनिंग टाइम का पालन करना चाहिए जब इनपुट का आकार बढ़ता है।
स्पेस कॉम्प्लेक्सिटी के लिए, हमारा लक्ष्य उस संबंध या फंक्शन को प्राप्त करना है कि एल्गोरिदम को पूरा करने के लिए मुख्य मेमोरी में कितना स्थान घेरता है।
एसिम्प्टोटिक व्यवहार
एक फंक्शन f(n) के लिए एसिम्प्टोटिक व्यवहार f(n) की वृद्धि है जब n बड़ा होता है। छोटे इनपुट मानों पर विचार नहीं किया जाता। हमारा कार्य यह पता लगाना है कि बड़े इनपुट मान के लिए कितना समय लगेगा।
उदाहरण के लिए, f(n) = c * n + k रैखिक समय जटिलता के रूप में। f(n) = c * n² + k द्विघात समय जटिलता है।
एल्गोरिदम का विश्लेषण तीन अलग-अलग मामलों में विभाजित किया जा सकता है। मामले निम्नानुसार हैं -
बेस्ट केस − यहां रनिंग टाइम की निचली सीमा की गणना की जाती है। यह इष्टतम स्थितियों में एक एल्गोरिदम के व्यवहार का वर्णन करता है।
एवरेज केस − इस मामले में हम एल्गोरिदम के रनिंग टाइम की ऊपरी और निचली सीमा के बीच के क्षेत्र की गणना करते हैं। इस मामले में निष्पादित ऑपरेशन की संख्या न तो न्यूनतम है और न ही अधिकतम।
वर्स्ट केस − इस मामले में हम एल्गोरिदम के रनिंग टाइम की ऊपरी सीमा की गणना करते हैं। इस मामले में अधिकतम संख्या में ऑपरेशन निष्पादित होते हैं।
