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