DAA - एल्गोरिदम का विश्लेषण
एल्गोरिदम के सैद्धांतिक विश्लेषण में, मनमाने ढंग से बड़े इनपुट के लिए जटिलता समारोह का अनुमान लगाने के लिए, स्पर्शोन्मुख अर्थों में उनकी जटिलता का अनुमान लगाना आम है। अवधि"analysis of algorithms" डोनाल्ड नुथ द्वारा गढ़ा गया था।
एल्गोरिथम विश्लेषण कम्प्यूटेशनल जटिलता सिद्धांत का एक महत्वपूर्ण हिस्सा है, जो एक विशिष्ट कम्प्यूटेशनल समस्या को हल करने के लिए एल्गोरिदम के आवश्यक संसाधनों के लिए सैद्धांतिक अनुमान प्रदान करता है। अधिकांश एल्गोरिदम को मनमानी लंबाई के इनपुट के साथ काम करने के लिए डिज़ाइन किया गया है। एल्गोरिदम का विश्लेषण इसे निष्पादित करने के लिए आवश्यक समय और अंतरिक्ष संसाधनों की मात्रा का निर्धारण है।
आमतौर पर, एल्गोरिथ्म की दक्षता या चलने का समय एक फ़ंक्शन के रूप में कहा जाता है, जो इनपुट लंबाई से संबंधित चरणों की संख्या से संबंधित है time complexity, या स्मृति की मात्रा, के रूप में जाना जाता है space complexity।
विश्लेषण की आवश्यकता है
इस अध्याय में, हम एल्गोरिदम के विश्लेषण की आवश्यकता पर चर्चा करेंगे और किसी विशेष समस्या के लिए एक बेहतर एल्गोरिदम का चयन कैसे करें क्योंकि एक कम्प्यूटेशनल समस्या को विभिन्न एल्गोरिदम द्वारा हल किया जा सकता है।
एक विशिष्ट समस्या के लिए एक एल्गोरिथ्म पर विचार करके, हम पैटर्न मान्यता को विकसित करना शुरू कर सकते हैं ताकि इस एल्गोरिथ्म की मदद से इसी प्रकार की समस्याओं को हल किया जा सके।
एल्गोरिदम अक्सर एक दूसरे से काफी अलग होते हैं, हालांकि इन एल्गोरिदम का उद्देश्य समान है। उदाहरण के लिए, हम जानते हैं कि विभिन्न एल्गोरिदम का उपयोग करके संख्याओं का एक सेट छांटा जा सकता है। एक एल्गोरिथ्म द्वारा की गई तुलनाओं की संख्या समान इनपुट के लिए दूसरों के साथ भिन्न हो सकती है। इसलिए, उन एल्गोरिदम की समय जटिलता भिन्न हो सकती है। उसी समय, हमें प्रत्येक एल्गोरिथ्म द्वारा आवश्यक मेमोरी स्पेस की गणना करने की आवश्यकता है।
एल्गोरिथ्म का विश्लेषण एल्गोरिथ्म की समस्या को सुलझाने की क्षमता का विश्लेषण करने की प्रक्रिया है समय और आकार के संदर्भ में आवश्यक है (कार्यान्वयन के दौरान भंडारण के लिए स्मृति का आकार)। हालांकि, एल्गोरिदम के विश्लेषण की मुख्य चिंता आवश्यक समय या प्रदर्शन है। आम तौर पर, हम निम्नलिखित प्रकार के विश्लेषण करते हैं -
Worst-case - आकार के किसी भी उदाहरण पर उठाए गए कदमों की अधिकतम संख्या a।
Best-case - आकार के किसी भी उदाहरण पर उठाए गए कदमों की न्यूनतम संख्या a।
Average case - आकार के किसी भी उदाहरण पर उठाए गए औसत कदम a।
Amortized - आकार के इनपुट पर लागू संचालन का एक क्रम a समय के साथ औसतन।
एक समस्या को हल करने के लिए, हमें समय के साथ-साथ अंतरिक्ष की जटिलता पर भी विचार करने की आवश्यकता है क्योंकि कार्यक्रम एक ऐसी प्रणाली पर चल सकता है जहां मेमोरी सीमित है लेकिन पर्याप्त स्थान उपलब्ध है या इसके विपरीत हो सकता है। इस संदर्भ में, यदि हम तुलना करते हैंbubble sort तथा merge sort। बबल सॉर्ट को अतिरिक्त मेमोरी की आवश्यकता नहीं होती है, लेकिन मर्ज सॉर्ट के लिए अतिरिक्त स्थान की आवश्यकता होती है। हालांकि मर्ज सॉर्ट की तुलना में बबल सॉर्ट की समय जटिलता अधिक है, लेकिन बबल सॉर्ट को लागू करने की आवश्यकता हो सकती है यदि प्रोग्राम को एक वातावरण में चलाने की आवश्यकता है, जहां मेमोरी बहुत सीमित है।