संकेतों और व्याख्याओं के साथ मुफ़्त एल्गोरिदम और जटिलता बहुविकल्पीय अभ्यास प्रश्न, तीन स्तरों पर: मुख्य शब्द और तथ्य, अवधारणाओं का अनुप्रयोग, केस और विश्लेषण।
बड़े n के लिए कौन-सा कॉम्प्लेक्सिटी क्लास सबसे तेज़ी से बढ़ता है?
बढ़िया काम। अगला प्रश्न चाहिए?अगले के लिए तैयार? हर विषय में हर दिन 5 नए प्रश्न।
एल्गोरिदम सटीक चरणों की एक परिमित सूची है जो किसी समस्या को हल करती है, जैसे किसी सूची को क्रमबद्ध करना या फ़ोन बुक में कोई नाम ढूँढना।
दो एल्गोरिदम एक ही समस्या हल कर सकते हैं पर बहुत अलग समय ले सकते हैं। जटिलता बताती है कि इनपुट बड़ा होने पर काम कैसे बढ़ता है।
इनपुट के आकार को n कहते हैं: क्रमबद्ध करने वाली वस्तुओं की संख्या, सूची की लंबाई, ग्राफ़ में नोडों की संख्या।
1000 पृष्ठों की फ़ोन बुक में कोई नाम ढूँढने की सोचें। हर पृष्ठ पढ़ने में 1000 चरण तक लगते हैं। बीच में खोलकर हर बार आधा करने में लगभग 10 चरण लगते हैं।
समय जटिलता चरण गिनती है। स्थान जटिलता अतिरिक्त मेमोरी गिनती है। दोनों n के फलन के रूप में लिखी जाती हैं।
आमतौर पर आप सबसे खराब स्थिति देखते हैं: आकार n के सभी इनपुटों में सबसे अधिक काम। कभी-कभी इसके बजाय औसत या सबसे अच्छी स्थिति पूछी जाती है।
उत्तर: 4 सेकंड. n को दोगुना करने से n², 2² = 4 से गुणा होता है, इसलिए समय लगभग 1 से लगभग 4 सेकंड हो जाता है। 2 सेकंड रैखिक वृद्धि का उत्तर होता, और 8, n³ का।
बिग O संकेतन केवल वही रखता है जो बड़े n के लिए मायने रखता है। आप अचर गुणक हटाते हैं और केवल सबसे तेज़ बढ़ने वाला पद रखते हैं।
n = 1000 के लिए n² पद 3 000 000 है, जबकि 5n केवल 5000 है। छोटे पद कुल को मुश्किल से बदलते हैं।
ये वर्ग बार-बार आते हैं, सबसे धीमी से सबसे तेज़ वृद्धि तक:
बिग O एक ऊपरी सीमा है: काम अधिकतम इतनी तेज़ी से बढ़ता है। Ω (बिग ओमेगा) निचली सीमा है, और Θ (थीटा) कसी हुई सीमा है, ऊपरी और निचली दोनों।
बिग O में लघुगणक का आधार मायने नहीं रखता, क्योंकि अलग-अलग आधारों वाले लघुगणक केवल एक अचर गुणक से भिन्न होते हैं।
उत्तर: O(n²). बड़े n के लिए n² पद प्रभावी है, और अचर गुणक 2 हटा दिया जाता है। O(n) गलत पद रखता है, और O(2n²) अचर हटाना भूल जाता है।
कुछ एल्गोरिदम लगभग हर पाठ्यक्रम में आते हैं। उनकी जटिलताएँ तथ्यों की तरह सीखें।
एक पुनरावर्ती फलन स्वयं को छोटे इनपुट पर तब तक बुलाता है जब तक वह किसी आधार स्थिति तक न पहुँचे जिसका वह सीधे उत्तर देता है। इसका चलने का समय एक पुनरावृत्ति संबंध के रूप में लिखा जाता है:
तीन डिज़ाइन विचार जानने योग्य हैं। विभाजन और विजय बाँटता, हल करता और मिलाता है। लालची (ग्रीडी) हर चरण में स्थानीय रूप से सबसे अच्छा विकल्प लेता है। गतिशील प्रोग्रामिंग अतिव्यापी उपसमस्याओं के उत्तर संग्रहीत करती है ताकि वे एक ही बार निकाले जाएँ।
उत्तर: O(n²). खराब पिवटों के साथ हर विभाजन एक ओर n − 1 वस्तुएँ छोड़ता है, जिससे O(n²) मिलता है। O(n log n) इसकी औसत स्थिति है, और मर्ज सॉर्ट की सबसे खराब स्थिति।
किसी कोड खंड की समय जटिलता ज्ञात करने के लिए:
सैद्धांतिक प्रश्न के लिए पहले उस एल्गोरिदम या विचार का नाम बताएँ जिसका वह वर्णन करता है, फिर उसकी जटिलता और शर्तें (क्रमबद्ध इनपुट, ऋणेतर भार, अतिव्यापी उपसमस्याएँ) याद करें।
हर चरण का अनुसरण करें। अगला चरण खोलने से पहले उसका अनुमान लगाने का प्रयास करें।
इस कोड की समय जटिलता क्या है? for i = 1 to n: (j = 1; while j < n: j = j × 2)
n वह संख्या है जहाँ तक लूप चलते हैं।
i, 1 से n तक 1 के चरणों में जाता है, इसलिए बाहरी लूप n बार चलता है।
j के मान 1, 2, 4, 8, … होते हैं और n तक पहुँचने पर रुकता है। k चक्रों के बाद j = 2k, इसलिए लूप लगभग log₂ n चक्रों के बाद रुकता है।
भीतरी लूप बाहरी लूप के अंदर है, इसलिए गिनतियाँ गुणा होती हैं।
n = 1024 के लिए भीतरी लूप log₂ 1024 = 10 बार चलता है, इसलिए मुख्य भाग 1024 · 10 = 10 240 बार चलता है। यह n² = 1 048 576 से बहुत कम है।
O(n log n)
उत्तर: O(n). एक के बाद एक चलने वाले लूप जुड़ते हैं: n + n = 2n, और अचर हटा दिया जाता है, इसलिए O(n)। O(n²) तभी सही होता जब एक लूप दूसरे के अंदर होता।
P में वे समस्याएँ हैं जो बहुपद समय में हल की जा सकती हैं। NP में वे समस्याएँ हैं जिनके हल बहुपद समय में जाँचे जा सकते हैं। P की हर समस्या NP में है; P = NP है या नहीं, यह अभी अज्ञात है।
कौन-सा नोटेशन वृद्धि की ऊपरी सीमा (upper bound) को दर्शाता है?
O ऊपरी सीमा, Ω निचली सीमा और Θ सटीक (tight) सीमा देता है।
एक सॉर्टेड ऐरे में आप दोनों सिरों से एक-एक पॉइंटर को भीतर की ओर खिसकाते हुए ऐसे दो तत्व खोजते हैं जिनका योग लक्ष्य के बराबर हो। टाइम कॉम्प्लेक्सिटी क्या है?
यदि योग बहुत छोटा हो तो बायाँ पॉइंटर दाएँ खिसकता है, बहुत बड़ा हो तो दायाँ पॉइंटर बाएँ, इसलिए अधिकतम n चरण होते हैं।
स्ट्रासेन का एल्गोरिदम आधे आकार के ब्लॉकों के 8 के बजाय 7 रिकर्सिव गुणनों से मैट्रिक्स गुणा करता है। इसका रनिंग टाइम क्या है?
a = 7 और b = 2 के साथ nlog₂ 7, O(n²) जोड़ कार्य पर प्रभावी होता है, जिससे लगभग n2.81 मिलता है।
दो एल्गोरिदम एक ही समस्या हल कर सकते हैं पर बहुत अलग समय ले सकते हैं। जटिलता बताती है कि इनपुट बड़ा होने पर काम कैसे बढ़ता है।
इनपुट के आकार को n कहते हैं: क्रमबद्ध करने वाली वस्तुओं की संख्या, सूची की लंबाई, ग्राफ़ में नोडों की संख्या।
हर प्रश्न में चार विकल्प होते हैं, और केवल एक सही होता है। अटक गए? पहले एक छोटा संकेत खोलें, और पूरी व्याख्या तभी जब ज़रूरत हो।