एल्गोरिथम जटिलता विश्लेषण का परिचय (भाग 4)

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

पहले प्रकाशित:
भाग 1
भाग २
भाग ३

इष्टतम छँटाई

बधाई! अब आप जानते हैं कि एल्गोरिदम की जटिलता का विश्लेषण कैसे किया जाता है, असममित अनुमान और संकेतन "बिग-ओ" क्या है। आप यह भी जानते हैं कि कैसे पता लगाना है कि एल्गोरिथ्म की जटिलता O( 1 ) , O( log( n ) ) , O( n ) , O( n ² ) और इसी तरह है। आप o , o , familiar, Θ , Θ और "सबसे खराब स्थिति" की अवधारणा से परिचित हैं। यदि आप इस जगह पर आते हैं, तो मेरे लेख ने पहले ही अपना काम पूरा कर लिया है।

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

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

इससे पहले कि हम वास्तविक मर्ज प्रकार को लागू करें, हमें एक सहायक फ़ंक्शन लिखना होगा। हम इसे merge कहते हैं, और इसे दो पहले से ही सॉर्ट किए गए सरणियों को लेने और उन्हें एक (भी सॉर्ट किए गए) में संयोजित करते हैं। यह करना आसान है:

 def merge( A, B ): if empty( A ): return B if empty( B ): return A if A[ 0 ] < B[ 0 ]: return concat( A[ 0 ], merge( A[ 1...A_n ], B ) ) else: return concat( B[ 0 ], merge( A, B[ 1...B_n ] ) ) 

concat फ़ंक्शन एक तत्व ("हेड") और एक एरे ("टेल") लेता है और उन्हें कॉन्कैट करता है, शेष एलिमेंट के रूप में एक "हेड" पहले तत्व और एक "टेल" के रूप में एक नया एरे देता है। उदाहरण के लिए, concat( 3, [ 4, 5, 6 ] ) [ 3, 4, 5, 6 ] वापस आएगा। हम क्रमशः A और B के सरणियों के आकार को निरूपित करने के लिए A_n और B_n का उपयोग करते हैं।



इस एल्गोरिथ्म के विश्लेषण से पता चलता है कि इसका निष्पादन समय Θ( n ) , जहां n परिणामी सरणी की लंबाई ( n = A_n + B_n ) है।



इस फ़ंक्शन का उपयोग करके, हम एक बेहतर सॉर्टिंग एल्गोरिथ्म का निर्माण कर सकते हैं। विचार यह है: हम सरणी को दो भागों में विभाजित करते हैं, उनमें से प्रत्येक को पुन: क्रमबद्ध करते हैं और दो क्रमबद्ध सरणियों को एक में जोड़ते हैं। छद्म कोड:

 def mergeSort( A, n ): if n = 1: return A # it is already sorted middle = floor( n / 2 ) leftHalf = A[ 1...middle ] rightHalf = A[ ( middle + 1 )...n ] return merge( mergeSort( leftHalf, middle ), mergeSort( rightHalf, n - middle ) ) 

यह फ़ंक्शन पिछले वाले की तुलना में समझना कठिन है, इसलिए अगला अभ्यास आपको अधिक समय लग सकता है।



अंतिम अभ्यास के रूप में, आइए mergeSort की जटिलता का विश्लेषण करें। प्रत्येक चरण पर, हम मूल सरणी को दो समान भागों ( binarySearch समान) में विभाजित करते हैं। हालांकि, इस मामले में आगे की गणना दोनों भागों पर होती है। पुनरावर्तन रिटर्न के बाद, हम merge ऑपरेशन को परिणामों पर लागू करते हैं, जिसमें Θ( n ) समय लगता है।

तो, हम मूल सरणी को दो भागों में विभाजित करते हैं, प्रत्येक n / 2 आकार में। जब हम उन्हें कनेक्ट करते हैं, तो n तत्व ऑपरेशन में भाग लेंगे, इसलिए, निष्पादन का समय Θ( n ) । नीचे दिया गया चित्र इस पुनरावृत्ति को दर्शाता है:



देखते हैं कि यहां क्या होता है। प्रत्येक सर्कल mergeSort फ़ंक्शन के लिए कॉल का प्रतिनिधित्व करता है। सर्कल में संख्या को सॉर्ट किए जाने वाले एरे में तत्वों की संख्या को इंगित करता है। शीर्ष नीला वृत्त आकार n की एक सरणी के लिए mergeSort करने की प्रारंभिक कॉल है। एरो फ़ंक्शंस के बीच पुनरावर्ती कॉल दिखाता है। mergeSort करने की मूल कॉल दो नए सरणियों को उत्पन्न करती है, प्रत्येक n / 2 आकार में। बदले में, उनमें से प्रत्येक n / 4 तत्वों के सरणियों के साथ दो और कॉल उत्पन्न करता है, और इसी तरह जब तक हमें एक आकार नहीं मिलता है। 1. इस आरेख को एक पुनरावर्ती पेड़ कहा जाता है, क्योंकि यह पुनरावृत्ति के संचालन को दिखाता है और एक पेड़ की तरह दिखता है। अधिक सटीक, शीर्ष पर एक जड़ के साथ एक पेड़ के उलटा के रूप में और तल पर छोड़ देता है)।

ध्यान दें कि प्रत्येक पंक्ति में तत्वों की संख्या n बराबर रहती है। यह भी ध्यान दें कि प्रत्येक कॉलिंग नोड merge ऑपरेशन के लिए बुलाया नोड्स से प्राप्त परिणामों का उपयोग करता है। उदाहरण के लिए, एक लाल नोड n / 2 आइटम को सॉर्ट करता है। ऐसा करने के लिए, यह n / 2 सरणी को n / 4 दो में विभाजित करता है, उनमें से प्रत्येक के साथ पुन: mergeSort (ग्रीन नोड्स) कहता है, और परिणामों को आकार n / 2 एक पूर्णांक में जोड़ता है।

नतीजतन, प्रत्येक पंक्ति की जटिलता Θ( n ) । हम जानते हैं कि इस तरह की रेखाओं की संख्या, जिसे पुनरावर्ती वृक्ष की गहराई कहा जाता है, log( n ) । इसका कारण वही तर्क हैं जो हमने बाइनरी सर्च के लिए इस्तेमाल किए थे। तो, हमारे पास log( n ) जटिलताएं Θ( n ) , इसलिए, mergeSort की सामान्य जटिलता: Θ( n * log( n ) ) । यह Θ( n ² ) से बहुत बेहतर है, जिसे पसंद द्वारा छांटना हमें देता है (याद रखें, log( n ) बहुत कम है, इसलिए n * log( n ) भी n * n = n ² ) से बहुत कम है)।

जैसा कि आपने पिछले उदाहरण में देखा था, जटिलता विश्लेषण हमें एल्गोरिदम की तुलना करने की अनुमति देता है कि कौन सा बेहतर है। इन विचारों के आधार पर, अब हम यह सुनिश्चित कर सकते हैं कि बड़े सरणियों के लिए, मर्ज सॉर्टिंग पसंद के हिसाब से बेहतर प्रदर्शन करेगा। इस तरह का निष्कर्ष समस्याग्रस्त होगा यदि हमारे पास हमारे द्वारा विकसित एल्गोरिदम के विश्लेषण के लिए सैद्धांतिक आधार नहीं था। निस्संदेह, रनटाइम Θ( n * log( n ) ) साथ छंटनी एल्गोरिदम व्यापक रूप से अभ्यास में उपयोग किया जाता है। उदाहरण के लिए, लिनक्स कर्नेल हीप सॉर्टिंग नामक एक एल्गोरिथ्म का उपयोग करता है , जिसमें मर्ज सॉर्ट के समान रनटाइम होता है। ध्यान दें कि हम इन छँटाई एल्गोरिदम की इष्टतमता साबित नहीं करेंगे। इसके लिए बहुत अधिक बोझिल गणितीय तर्कों की आवश्यकता होगी, लेकिन सुनिश्चित करें: जटिलता के दृष्टिकोण से, एक बेहतर विकल्प खोजना असंभव है।

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

एक निष्कर्ष के बजाय

यह लेख क्रिएटिव कॉमन्स 3.0 एट्रीब्यूशन के तहत प्रकाशित हुआ है। इसका मतलब है कि आप इसे कॉपी कर सकते हैं, इसे अपनी वेबसाइटों पर प्रकाशित कर सकते हैं, पाठ में बदलाव कर सकते हैं, और आम तौर पर आप इसे पसंद करते हैं। बस मेरा नाम बताना न भूलें। केवल एक चीज: यदि आप इस पाठ पर अपने काम को आधार बनाते हैं, तो मैं आपसे आग्रह करता हूं कि इसे सहयोग और सूचना के प्रसार की सुविधा के लिए क्रिएटिव कॉमन्स के तहत प्रकाशित करें।

अंत तक पढ़ने के लिए धन्यवाद!

संदर्भ

1. कॉर्मेन, लिसेर्सन, रिवेस्ट, स्टीन। एल्गोरिदम का परिचय , एमआईटी प्रेस
2. दासगुप्ता, पापादिमित्रिउ, वज़ीरानी। एल्गोरिदम , मैकग्रा-हिल प्रेस
3. Fotakis। एथेंस के राष्ट्रीय तकनीकी विश्वविद्यालय में असतत गणित का कोर्स
4. Fotakis। एथेंस के राष्ट्रीय तकनीकी विश्वविद्यालय में एल्गोरिथम और जटिलता का पाठ्यक्रम