एल्गोरिदम के सैद्धांतिक विश्लेषण में, उनकी जटिलता का अनुमान एसिम्प्टोटिक अर्थ में लगाना आम है, यानी मनमाने ढंग से बड़े इनपुट के लिए जटिलता फंक्शन का अनुमान लगाना। "एल्गोरिदम का विश्लेषण" शब्द डोनाल्ड नुथ द्वारा गढ़ा गया था।
एल्गोरिदम विश्लेषण कम्प्यूटेशनल कॉम्प्लेक्सिटी थ्योरी का एक महत्वपूर्ण हिस्सा है, जो एक विशिष्ट कम्प्यूटेशनल समस्या को हल करने के लिए एल्गोरिदम के आवश्यक संसाधनों के लिए सैद्धांतिक अनुमान प्रदान करता है। अधिकांश एल्गोरिदम मनमाने लंबाई के इनपुट के साथ काम करने के लिए डिज़ाइन किए गए हैं। एल्गोरिदम का विश्लेषण इसे निष्पादित करने के लिए आवश्यक समय और स्थान संसाधनों का निर्धारण है।
आमतौर पर, एक एल्गोरिदम की दक्षता या रनिंग टाइम को एक फंक्शन के रूप में बताया जाता है जो इनपुट लंबाई को चरणों की संख्या से संबंधित करता है, जिसे टाइम कॉम्प्लेक्सिटी के रूप में जाना जाता है, या मेमोरी की मात्रा, जिसे स्पेस कॉम्प्लेक्सिटी के रूप में जाना जाता है।
इस सेक्शन में हम कवर करेंगे -
- एल्गोरिदम और कॉम्प्लेक्सिटी
- एसिम्प्टोटिक एनालिसिस
- एसिम्प्टोटिक नोटेशन
- एमोर्टाइज़्ड एनालिसिस
- स्पेस कॉम्प्लेक्सिटी
- स्यूडो पॉलीनोमियल टाइप एल्गोरिदम और PATS (स्यूडो पॉलीनोमियल टाइप अप्रॉक्सिमेशन स्कीम)
