एल्गोरिथम विश्लेषण

विश्लेषण क्या है?
एल्गोरिथ्म का विश्लेषण करके, आप यह अनुमान लगा सकते हैं कि इस एल्गोरिथ्म का उपयोग करके इस समस्या को हल करने में कितना समय लगेगा। एक ही समस्या को विभिन्न एल्गोरिदम का उपयोग करके हल किया जा सकता है। एल्गोरिथ्म विश्लेषण हमें एक एल्गोरिथ्म का चयन करने के लिए एक उपकरण देता है।
एल्गोरिदम के विश्लेषण का परिणाम सेकंड या कंप्यूटर चक्रों की सटीक संख्या के लिए एक सूत्र नहीं है जो किसी विशेष एल्गोरिथ्म की आवश्यकता होगी। आपको यह समझने की आवश्यकता है कि एल्गोरिथ्म के बीच का अंतर जो N + 5 संचालन करता है और जो N + 250 संचालन करता है वह N बहुत बड़े होते ही अदृश्य हो जाता है।


इनपुट कक्षाएं
एल्गोरिथ्म का विश्लेषण करते समय, इनपुट डेटा का विकल्प इसके निष्पादन को महत्वपूर्ण रूप से प्रभावित कर सकता है। मान लीजिए कि कुछ छंटाई एल्गोरिदम बहुत तेज़ी से काम कर सकते हैं यदि इनपुट सूची पहले से ही क्रमबद्ध है, जबकि अन्य एल्गोरिदम ऐसी सूची में बहुत मामूली परिणाम दिखाएंगे। लेकिन एक यादृच्छिक सूची में, परिणाम विपरीत हो सकता है। इसलिए, हम एकल इनपुट डेटा सेट पर एल्गोरिदम के व्यवहार का विश्लेषण करने के लिए खुद को सीमित नहीं करेंगे। व्यवहार में, आपको डेटा की तलाश करनी होगी जो एल्गोरिथम का सबसे तेज़ और धीमा निष्पादन प्रदान करता है। इसके अलावा, सभी संभव डेटा सेटों पर एल्गोरिथ्म की औसत दक्षता का मूल्यांकन करना उपयोगी है।

सबसे अच्छा मामला

सबसे अच्छा मामले में एल्गोरिथ्म निष्पादन समय अक्सर बहुत छोटा या बस स्थिर होता है, इसलिए ऐसा विश्लेषण शायद ही कभी किया जाता है।

सबसे खराब मामला

सबसे खराब मामला विश्लेषण अत्यंत महत्वपूर्ण है क्योंकि यह आपको एल्गोरिथ्म के अधिकतम चलने के समय की कल्पना करने की अनुमति देता है। सबसे खराब स्थिति का विश्लेषण करते समय, आपको उस इनपुट को खोजने की आवश्यकता होती है जिस पर एल्गोरिदम सबसे अधिक काम करेगा।

मध्यम मामला

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


जहाँ n इनपुट डेटा के आकार को दर्शाता है, m समूहों की संख्या को दर्शाता है। pi के माध्यम से, इनपुट डेटा संख्या i के साथ समूह की संभावना है, और ti के माध्यम से, एल्गोरिथ्म के लिए समूह i से संख्या के साथ डेटा संसाधित करने के लिए आवश्यक समय है।

ज्यादातर मामलों में, हम मानेंगे कि प्रत्येक समूह में इनपुट डेटा गिरने की संभावनाएं समान हैं। दूसरे शब्दों में, यदि पाँच समूह हैं, तो पहले समूह में आने की संभावना वही है जो दूसरे में होने की संभावना है, आदि, अर्थात् संभावना
प्रत्येक समूह में होना 0.2 है। इस स्थिति में, औसत ऑपरेटिंग समय या तो पिछले सूत्र का उपयोग करके अनुमानित किया जा सकता है, या समकक्ष सूत्र का उपयोग कर सकता है


निचली सीमा। निर्णय का पेड़।
एल्गोरिथ्म इष्टतम है अगर कोई अन्य एल्गोरिथ्म जो इस समस्या को हल करता है, इससे अधिक तेजी से काम नहीं करता है। एक एल्गोरिथ्म की इष्टतमता का पता लगाने के लिए कैसे? ऐसा करने के लिए, हमें समस्या को हल करने के लिए आवश्यक संचालन की न्यूनतम संख्या पता होनी चाहिए, जिसे निचली सीमा कहा जाता है। लेकिन इसके लिए हमें TASK का अध्ययन करने की आवश्यकता है, न कि विशिष्ट एल्गोरिथ्म की!
एक उदाहरण के रूप में, एक द्विआधारी वृक्ष का उपयोग करके 3 संख्याओं की सूची को छाँटने की प्रक्रिया के विश्लेषण पर विचार करें। ऐसे वृक्ष को निर्णय वृक्ष कहा जाता है।


इस पेड़ में सबसे लंबा रास्ता सबसे खराब स्थिति से संबंधित है और इसके विपरीत, सबसे छोटा से सबसे अच्छा है। औसत मामले को शीट की संख्या से पेड़ में किनारों की संख्या को विभाजित करने के भागफल के रूप में वर्णित किया गया है।
2 तत्वों के पुनर्व्यवस्था के लिए, हमारे पास 1 शीट है, एन तत्वों के लिए, कॉम्बिनेटरिक्स के नियमों के अनुसार, एन! चादरें। स्तर K पर शीटों की संख्या 2k-1 है, इसलिए, हमारे निर्णय वृक्ष में L- स्तर होंगे, जहां L, N का सबसे छोटा पूर्णांक है! 1 2L-1। लघुगणक, हम प्राप्त करते हैं



अंत में, हम प्राप्त करते हैं:

इसलिए हमने सीखा कि ऑर्डर O (NlgN) का कोई भी सॉर्टिंग एल्गोरिथ्म सबसे अच्छा है और इसे इष्टतम माना जा सकता है। इसके अलावा, इस अध्ययन से यह पता चलता है कि एक एल्गोरिथ्म जो ओ (एनएलजीएन) संचालन की तुलना में तेजी से छंटनी की समस्या को हल करता है, सही ढंग से काम नहीं कर सकता है!