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

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

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

जटिलता

पिछले भाग से, हम यह निष्कर्ष निकाल सकते हैं कि यदि हम इन सभी सजावटी स्थिरांक को त्याग सकते हैं, तो प्रोग्राम निर्देशों की गिनती के लिए फ़ंक्शन के विषम व्यवहार के बारे में बात करना बहुत सरल होगा। वास्तव में, किसी भी प्रोग्राम जिसमें लूप नहीं होते हैं, में f( n ) = 1 , क्योंकि इस मामले में लगातार निर्देशों की आवश्यकता होती है (बेशक, पुनरावृत्ति की अनुपस्थिति में - नीचे देखें)। 1 से n तक का एक एकल चक्र asymptotics f( n ) = n , क्योंकि चक्र से पहले और बाद में यह अपरिवर्तित संख्याओं को निष्पादित करता है, जबकि चक्र के अंदर निर्देशों की निरंतर संख्या n बार निष्पादित होती है।

इस तरह के विचार से निर्देशित हर बार निर्देशों को पढ़ने की तुलना में कम थकाऊ होता है, तो आइए इस सामग्री को समेकित करने के लिए कुछ उदाहरण देखें। निम्न PHP प्रोग्राम यह देखने के लिए जाँचता है कि क्या सरणी A आकार n में दिए गए मान हैं:

 <?php $exists = false; for ( $i = 0; $i < n; ++$i ) { if ( $A[ $i ] == $value ) { $exists = true; break; } } ?> 

किसी सरणी के अंदर मान खोजने की इस विधि को रैखिक खोज कहा जाता है। यह एक मान्य नाम है क्योंकि कार्यक्रम में f( n ) = n (जिसका अर्थ है "रैखिक" अधिक सटीक रूप से, हम अगले अनुभाग में विचार करेंगे)। break एक प्रोग्राम को एक एकल पुनरावृत्ति के बाद भी बाहर निकलने की अनुमति देता है। हालांकि, मैं आपको याद दिलाता हूं कि हम सबसे प्रतिकूल परिदृश्य में रुचि रखते हैं, जिसमें सरणी A में दिए गए मान बिल्कुल नहीं होते हैं। इसलिए, f( n ) = n पहले की तरह।



आइए एक पायथन प्रोग्राम को देखें, जो एक सरणी से दो मान जोड़ता है और एक नए चर के लिए परिणाम लिखता है:

 v = a[ 0 ] + a[ 1 ] 

यहां हमारे पास लगातार निर्देशों की संख्या है, इसलिए f( n ) = 1 ।

निम्न C ++ प्रोग्राम यह देखने के लिए जाँच करता है कि क्या वेक्टर (मूल सरणी) A आकार n में दो समान मान हैं:

 bool duplicate = false; for ( int i = 0; i < n; ++i ) { for ( int j = 0; j < n; ++j ) { if ( i != j && A[ i ] == A[ j ] ) { duplicate = true; break; } } if ( duplicate ) { break; } } 

दो नेस्टेड चक्र हमें फॉर्म f( n ) = n ^{2 के} एसिम्पोटिक्स देते हैं।

---

व्यावहारिक सिफारिश : सरल कार्यक्रमों का विश्लेषण उन में नेस्टेड चक्रों की संख्या की गणना करके किया जा सकता है। n पुनरावृत्तियों में एक एकल चक्र f( n ) = n । लूप के अंदर लूप f( n ) = n ^{2 है} । चक्र के अंदर का चक्र f( n ) = n ^{3 है} । और इसी तरह।

---

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

 int i; for ( i = 0; i < n; ++i ) { f( n ); } 

यदि हम जानते हैं कि f( n ) बिल्कुल n निर्देशों को निष्पादित करता है, तो हम कह सकते हैं कि पूरे कार्यक्रम में निर्देशों की संख्या n ^{2 तक} पहुंच जाती है, क्योंकि f( n ) को n समय कहा जाता है।

---

व्यावहारिक सिफारिश : यदि हमारे पास लगातार लूप्स की एक श्रृंखला है, तो कार्यक्रम का असममित व्यवहार उनमें से सबसे धीमा निर्धारित करता है। एक के बाद दो नेस्टेड लूप समान रूप से समान हैं जैसे नेस्टेड लूप्स खुद को। नेस्टेड लूप्स को सिंगल लूप पर हावी होने के लिए कहा जाता है।

---

अब सिद्धांतकारों द्वारा उपयोग किए जाने वाले दिलचस्प अंकन पर स्विच करते हैं। जब हमें पता चलता है कि f का सटीक स्पर्शोन्मुखता है, तो हम कहते हैं कि हमारा कार्यक्रम Θ( f( n ) ) । उदाहरण के लिए, ऊपर दिए गए उदाहरणों में, क्रमशः कार्यक्रम, Θ( 1 ) , Θ( n ² ) और Θ( n ² ) । Θ( n ) उच्चारण "थीटा एन से होता है।" कभी-कभी हम कहते हैं कि f( n ) (स्थिरांक सहित निर्देश की गणना का मूल कार्य f( n ) that Θ( - ) । उदाहरण के लिए, हम कह सकते हैं कि f( n ) = 2n एक फ़ंक्शन है जो say Θ( n ) । सामान्य तौर पर, कुछ भी नया नहीं है। आप यह भी लिख सकते हैं कि 2n ∈ Θ( n ) , जिसका उच्चारण है: "दो n का थाटा से n" है। आपको इस तरह के संकेतन से भ्रमित नहीं होना चाहिए: यह केवल यह कहता है कि यदि हम प्रोग्राम के लिए आवश्यक कमांड की संख्या की गणना करते हैं और यह 2n होगा, तो इस एल्गोरिथम के स्पर्शोन्मुख व्यवहार को n रूप में वर्णित किया जाता है (जिसे हम निरंतर को त्याग कर पाते हैं)। अंकन की इस प्रणाली के बाद, हम कुछ सच्चे गणितीय कथन देते हैं:

1. एन ⁶ + 3 एन Θ Θ (एन ⁶ )
2. 2 ^एन + 12 ∈ ∈ (2 ^एन )
3. 3 ^एन + 2 ^एन Θ Θ (3 ^एन )
4. n ⁿ + n n Θ (n ⁿ )

वैसे, यदि आपने पहले भाग में से 1 का अभ्यास करने का निर्णय लिया है, तो यह उसका सही उत्तर है।

हम इस फ़ंक्शन को कहते हैं (यानी हम जो लिखते Θ( ) ) समय जटिलता , या बस हमारे एल्गोरिथ्म की जटिलता । इस प्रकार, Θ( n ) साथ एक एल्गोरिथ्म में जटिलता n । Θ( 1 ) , Θ( n ) , Θ( n ² ) और Θ( log( n ) ) लिए विशेष नाम भी हैं, क्योंकि वे बहुत आम हैं। वे कहते हैं कि algorithm Θ( 1 ) एक निरंतर-समय एल्गोरिथ्म है, Θ( n ) रैखिक है , Θ( n ² ) द्विघात है , और Θ( log( n ) ) लघुगणक है (चिंता न करें यदि आप अभी भी नहीं जानते कि क्या है) लघुगणक - हम जल्द ही इस बारे में बात करेंगे)।

---

व्यावहारिक सिफारिश : एक छोटे smaller की तुलना में बड़े recommend रन धीमी के साथ कार्यक्रम।

---

संकेतन "बड़ा हे"

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

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

 b = [] n.times do m = a[ 0 ] mi = 0 a.each_with_index do |element, i| if element < m m = element mi = i end end a.delete_at( mi ) b << m end 

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

इस पद्धति को चयन द्वारा सॉर्ट कहा जाता है। सबसे पहले, सरणी का न्यूनतम तत्व पाया जाता है (ऊपर दिए गए कोड में। न्यूनतम को m रूप में दर्शाया जाता है, और इसके सूचकांक को mi रूप में), जो नए सरणी (हमारे मामले में b ) के अंत में रखा गया है और मूल से हटा दिया गया है। फिर, शेष मानों के बीच, न्यूनतम फिर से पाया जाता है, नए सरणी में जोड़ा जाता है (जिसमें अब दो मूल्य हैं) और पुराने से हटा दिया गया है। प्रक्रिया को तब तक दोहराया जाता है जब तक सभी तत्वों को मूल से एक नए सरणी में स्थानांतरित नहीं किया जाता है, जिसका अर्थ है कि सॉर्ट का अंत। हमारे उदाहरण में, हमारे पास दो नेस्टेड लूप हैं। बाहरी लूप n बार "रन" करता है, और सरणी के प्रत्येक तत्व के लिए एक बार आंतरिक लूप। चूँकि शुरू में n तत्व होते हैं और प्रत्येक पुनरावृत्ति पर हम उनमें से एक को हटाते हैं, तो पहले आंतरिक लूप "स्क्रॉल" n बार, फिर n - 1 , n - 2 और इसी तरह, जब तक कि अंतिम पुनरावृत्ति आंतरिक लूप केवल एक बार पास नहीं हो जाता।

यदि हम योग 1 + 2 + ... + (n - 1) + n , तो इस कोड की जटिलता का पता लगाना कुछ समस्याग्रस्त होगा। लेकिन हम इसके लिए एक "ऊपरी सीमा" पा सकते हैं। ऐसा करने के लिए, हम प्रोग्राम को बदल देंगे (आप मानसिक रूप से, कोड को छूए बिना) इसे इससे भी बदतर बना सकते हैं, और फिर जो हुआ उसके लिए जटिलता प्राप्त कर सकते हैं। फिर यह आत्मविश्वास से कहना संभव होगा कि मूल कार्यक्रम या तो बुरी तरह से काम करता है, या (सबसे अधिक संभावना है) बेहतर।

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

लेकिन विपरीत हमेशा सच नहीं होता है। उदाहरण के लिए, Θ( n ) के साथ कोई भी कोड O( n ) के अलावा O( n ² ) भी है। अगर हम कल्पना करते हैं कि Θ( n ) प्रोग्राम सिर्फ एक लूप के for है जो n बार चलता है, तो हम इसे दूसरे के for अंदर से जोड़कर और भी बुरा बना सकते हैं। यह f( n ) = n ^{2 के} साथ एक कार्यक्रम देगा। सारांश: किसी भी प्रोग्राम Θ( a ) के साथ O( b ) से भी खराब है। ध्यान दें कि परिवर्तन को मूल के समान अर्थ बनाने या कोड बनाने की आवश्यकता नहीं है। उसके लिए आवश्यक सभी निर्देशों को दिए गए n संबंध में निर्देशों की संख्या में वृद्धि करना है। हम परिणाम का उपयोग निर्देशों को गिनने के लिए करते हैं, समस्या को हल करने के लिए नहीं।

इसलिए, यह कहते हुए कि कार्यक्रम में O( n ² ) , हम सुरक्षित हैं: एल्गोरिथ्म के विश्लेषण से पता चला कि यह n ² से भी बदतर काम नहीं करेगा। इससे हमें अंदाजा होता है कि हमारा कार्यक्रम कितना तेज है। आइए कुछ उदाहरणों को हल करें ताकि आप नए अंकन के साथ बेहतर हों।





चूंकि एल्गोरिथ्म का जटिलता इसकी वास्तविक जटिलता की ऊपरी सीमा है , जो बदले में, say द्वारा दर्शाया जाता है, कभी-कभी हम कहते हैं कि Θ हमें एक सटीक अनुमान देता है। अगर हम जानते हैं कि हमें जो सीमा मिली है, वह सटीक नहीं है, तो हम इसे दर्शाने के लिए लोअरकेस का उपयोग कर सकते हैं। उदाहरण के लिए, यदि एल्गोरिथ्म Θ( n ) , तो इसकी सटीक जटिलता n । इसलिए, यह एल्गोरिथ्म एक ही समय में O( n ) और O( n ² ) । चूंकि एल्गोरिथ्म the Θ( n ) , O( n ) सीमा को अधिक सटीक रूप से परिभाषित करता है। और O( n ² ) हम ( n ² ) रूप में लिख सकते हैं (उच्चारण: "n वर्ग का छोटा ओ") यह दिखाने के लिए कि हम सीमा की गैर-कठोरता के बारे में जानते हैं। बेशक, यह बेहतर है जब हम अपने एल्गोरिथ्म के लिए सटीक सीमाओं को पा सकते हैं ताकि इसके व्यवहार के बारे में अधिक जानकारी हो, लेकिन, दुर्भाग्य से, यह करना हमेशा आसान नहीं होता है।

---

व्यावहारिक सिफारिश : एक एल्गोरिथ्म की O जटिलता का पता लगाने के लिए इसकी Θ जटिलता की तुलना में सरल है।

---

अब तक, आप पहले से ही इन सभी नई धारणाओं के साथ भ्रमित हो सकते हैं, लेकिन आइए अगले उदाहरणों पर जाने से पहले दो और पात्रों को जानें। ऊपर, हमने अपने कार्यक्रम को बदतर बनाने के लिए (निर्देश की संख्या में वृद्धि की और, इस प्रकार, निष्पादन का समय) बनाया, ओ-नोटेशन की तुलना में। हमें बताता है कि हमारा कोड एक निश्चित सीमा से कभी धीमा नहीं चलेगा। इससे हमें मूल्यांकन का आधार मिलता है: क्या हमारा कार्यक्रम काफी अच्छा है? यदि हम इसके विपरीत करते हैं, तो मौजूदा कोड को बेहतर बनाते हुए, और जो कुछ होता है उसकी जटिलता का पता लगाता है, तो हम Ω-नोटेशन का उपयोग करते हैं। इस प्रकार,, हमें जटिलता प्रदान करता है, जो हमारा कार्यक्रम बेहतर नहीं हो सकता। यह उपयोगी है अगर हम यह साबित करना चाहते हैं कि कार्यक्रम धीमा है या एल्गोरिथ्म खराब है। इसका उपयोग तब भी किया जा सकता है जब हम कहते हैं कि एल्गोरिथ्म इस विशेष मामले में उपयोग करने के लिए बहुत धीमा है। उदाहरण के लिए, यह कहना कि एल्गोरिथ्म Ω( n ³ ) अर्थ है कि एल्गोरिथ्म n ³ से बेहतर नहीं है। यह Θ( n ³ ) , या Θ( n ⁴ ) , या इससे भी बदतर हो सकता है, लेकिन हम इसकी "अच्छाई" की सीमा को जानेंगे। इस प्रकार,, हमें हमारे एल्गोरिथ्म की जटिलता पर एक कम बाध्य देता है। इसी तरह ο , हम ω लिख सकते हैं यदि हम जानते हैं कि यह सीमा सख्त नहीं है। उदाहरण के लिए, example Θ( n ³ ) एल्गोरिदम ο( n ⁴ ) और ω( n ² ) । Ω( n ) उच्चारण "ओमेगा बड़े एन से" है, जबकि ω( n ) उच्चारण "ओ से छोटा ओ" है।



हम because के बजाय O और and का उपयोग करते हैं Θ क्योंकि हम उन सीमाओं की सटीकता के बारे में सुनिश्चित नहीं हो सकते हैं जो हमने Θ हैं या केवल एल्गोरिथम को गहराई से खोदना नहीं चाहते हैं।

यदि आपको इस सभी प्रकार की अधिसूचनाओं को पूरी तरह से याद नहीं है, तो चिंता न करें। आप हमेशा वापस आ सकते हैं और उन पर जानकारी ताज़ा कर सकते हैं। सबसे महत्वपूर्ण वर्ण O और O हैं।

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

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

विषम अनुमानों के लिए तुलना ऑपरेटर	संख्या तुलना ऑपरेटर
एल्गोरिथ्म ओ (कुछ) है	किसी चीज का नंबर <
एल्गोरिथ्म हे (कुछ)	संख्या ≤ कुछ
एल्गोरिथ्म gorith है (कुछ)	संख्या = कुछ
एल्गोरिथ्म Ω (कुछ) है	संख्या ≥ कुछ
एल्गोरिथ्म gorith है (कुछ)	नंबर > कुछ

---

व्यावहारिक सलाह : तथ्य यह है कि सभी पात्रों के बावजूद O, o, Ω, ωऔर Θआवश्यक समय-समय पर कर रहे हैं, Oसबसे अधिक बार प्रयोग किया जाता है क्योंकि यह आसान से मिल रहा है Θ, और की तुलना में व्यवहार में अधिक उपयोगी है Ω।

---