एक सवाल, कई एल्गोरिदम
एल्गोरिदम किसी सवाल को हल करने के पक्के कदमों की सूची है। ज़्यादातर सवाल एक से ज़्यादा एल्गोरिदम से हल हो सकते हैं। जैसे सूची में नाम ढूँढना: हर नाम देखो, या (अगर सूची छँटी है) बार-बार आधा करो।
दोनों सही उत्तर देते हैं। फ़र्क दक्षता (efficiency) में है: कितना काम और कितनी मेमोरी लगती है। अच्छा प्रोग्रामर वह एल्गोरिदम चुनता है जो बड़े डेटा पर भी तेज़ रहे।
समय के आधार पर तुलना
स्टॉपवॉच से नापना ठीक नहीं: तेज़ कंप्यूटर धीमे एल्गोरिदम को भी अच्छा दिखा देता है। इसलिए हम इनपुट के आकार n के हिसाब से मूल कदम (तुलना, अदला-बदली, जोड़) गिनते हैं।
सबसे अच्छा, औसत और सबसे खराब केस
बेस्ट केस सबसे किस्मत वाला इनपुट है (13 पहले डिब्बे में: 1 कदम)। वर्स्ट केस सबसे बुरा (13 है ही नहीं: n कदम)। हम आमतौर पर वर्स्ट केस बताते हैं, क्योंकि यह एक वादा है: इससे धीमा कभी नहीं होगा।
टाइम और स्पेस कॉम्प्लेक्सिटी
टाइम कॉम्प्लेक्सिटी बताती है कि n बढ़ने पर कदम कैसे बढ़ते हैं। स्पेस कॉम्प्लेक्सिटी बताती है कि अतिरिक्त मेमोरी कैसे बढ़ती है। मर्ज सॉर्ट तेज़ है पर ज़्यादा मेमोरी लेता है; बबल सॉर्ट कम मेमोरी लेता है पर धीमा है।
बिग O नोटेशन
बिग O बढ़त की दर बताता है, छोटी बातों को छोड़कर। सिर्फ सबसे बड़ा पद रखो और स्थिर संख्याएँ हटाओ: 3n² + 5n + 2 बन जाता है O(n²), क्योंकि बड़े n पर लगभग सारा काम n² वाला हिस्सा करता है।
| बिग O | नाम | n = 16 | n = 1000 | उदाहरण |
|---|---|---|---|---|
| O(1) | स्थिर | 1 | 1 | ऐरे का 5वाँ आइटम पढ़ना |
| O(log n) | लघुगणकीय | 4 | लगभग 10 | बाइनरी सर्च |
| O(n) | रैखिक | 16 | 1000 | लीनियर सर्च, सबसे बड़ा ढूँढना |
| O(n log n) | n log n | 64 | लगभग 10,000 | मर्ज सॉर्ट |
| O(n²) | द्विघाती | 256 | 10,00,000 | बबल सॉर्ट, लूप के अंदर लूप |
कोड के लिए आसान नियम: n पर एक लूप = O(n); लूप के अंदर लूप = O(n²); हर बार सवाल आधा = O(log n)।
लीनियर और बाइनरी सर्च की दक्षता
लीनियर सर्च एक-एक करके देखता है। वर्स्ट केस: n तुलना, यानी O(n)। यह किसी भी सूची पर चलता है।
बाइनरी सर्च को छँटी हुई सूची चाहिए। बीच वाला देखो; बड़ा है तो दायाँ आधा हटाओ, वरना बायाँ। हर कदम सूची आधी होती है, इसलिए वर्स्ट केस लगभग log₂ n + 1 तुलना: O(log n)। 10 लाख आइटम पर सिर्फ लगभग 20 कदम।
सॉर्टिंग एल्गोरिदम की दक्षता
बबल, इंसर्शन और सिलेक्शन सॉर्ट में लूप के अंदर लूप होता है, इसलिए लगभग n²/2 तुलना: O(n²)। छँटी हुई सूची पर इंसर्शन सॉर्ट O(n) (बेस्ट केस) है।
मर्ज सॉर्ट सूची को लगभग log₂ n बार आधा करता है और हर स्तर पर लगभग n काम करता है: O(n log n)। इसे O(n) अतिरिक्त मेमोरी चाहिए।
अगर सिर्फ एक बार ढूँढना है, तो पहले छाँटना (n log n) एक लीनियर सर्च (n) से महँगा है। बार-बार ढूँढना हो तो एक बार छाँटना फ़ायदेमंद है।
प्रीकंडीशन, पोस्टकंडीशन और रिकर्शन की गलतियाँ
प्रीकंडीशन वह शर्त है जो शुरू होने से पहले सच होनी चाहिए (बाइनरी सर्च: सूची छँटी हो)। पोस्टकंडीशन वह वादा है जो अंत में पूरा होता है (सॉर्टिंग: हर आइटम अगले से छोटा या बराबर)। इन्हें लिखने से टेस्ट करना आसान होता है।
रिकर्शन में फ़ंक्शन छोटे सवाल पर खुद को बुलाता है। आम गलतियाँ:
- बेस केस नहीं, या ऐसा बेस केस जो कभी नहीं आता: कॉल रुकती ही नहीं (स्टैक ओवरफ़्लो)।
- हर कॉल में सवाल छोटा नहीं होता।
- एक ही काम बार-बार: सीधा रिकर्सिव फ़िबोनाची fib(3) को कई बार बुलाता है, लगभग O(2ⁿ)। उत्तर याद रखने (मेमोइज़ेशन) से यह O(n) हो जाता है।
- बहुत गहरा रिकर्शन बहुत मेमोरी लेता है, हर कॉल का एक स्टैक फ़्रेम।
करके देखो: दो सर्च की दौड़
1 से 32 तक संख्याएँ पर्चियों पर लिखो और क्रम में उल्टा रखो। दोस्त से एक गुप्त संख्या चुनवाओ। पहले एक-एक पर्ची पलटकर ढूँढो और गिनो। फिर हमेशा बीच वाली पर्ची पलटकर ढूँढो। 5 बार करो। किस तरीके में कभी 6 से ज़्यादा बार नहीं पलटना पड़ा? आखिरी 3D कदम में स्लाइडर से जाँचो (n = 32: log₂ 32 = 5)।
मुख्य सूत्र और परिभाषाएँ
- लीनियर सर्च: वर्स्ट केस n तुलना → O(n)
- बाइनरी सर्च: वर्स्ट केस लगभग log₂ n + 1 तुलना → O(log n)
- बबल / इंसर्शन / सिलेक्शन सॉर्ट: लगभग n(n − 1)/2 तुलना → O(n²)
- मर्ज सॉर्ट: लगभग n log₂ n तुलना → O(n log n)
- बिग O नियम: सबसे बड़ा पद रखो, स्थिरांक हटाओ (5n² + 3n → O(n²))
- n दोगुना: O(1) वही, O(log n) +1, O(n) ×2, O(n²) ×4
हल किए गए उदाहरण
1. सूची में 50 नाम हैं। लीनियर सर्च में बेस्ट और वर्स्ट केस में कितनी तुलना?
बेस्ट केस: नाम पहला है → 1 तुलना। वर्स्ट केस: नाम आखिरी है या है ही नहीं → 50 तुलना। लीनियर सर्च O(n) है।
2. 1024 आइटम की छँटी सूची में बाइनरी सर्च को ज़्यादा से ज़्यादा कितनी तुलना चाहिए?
हर कदम आधा: 1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1। यह 10 बार आधा करना है, और आखिरी जाँच: ज़्यादा से ज़्यादा 11 तुलना (log₂ 1024 = 10)।
3. f(n) = 4n² + 10n + 7 का बिग O बताओ।
सबसे बड़ा पद 4n² रखो और 4 हटाओ: O(n²)।
4. i का लूप 1 से n तक, उसके अंदर j का लूप 1 से n तक। अंदर की लाइन कितनी बार चलेगी?
i के n मानों में से हर एक के लिए n बार: n × n = n²। टाइम कॉम्प्लेक्सिटी O(n²)।
5. एक O(n²) प्रोग्राम 1000 आइटम 2 सेकंड में छाँटता है। 3000 आइटम में लगभग कितना समय?
n 3 गुना, तो n² 3² = 9 गुना: लगभग 2 × 9 = 18 सेकंड।
6. n = 1000 पर बबल सॉर्ट और मर्ज सॉर्ट की तुलना करो।
बबल: लगभग n²/2 = 5,00,000 तुलना। मर्ज: लगभग n log₂ n = 1000 × 10 = 10,000। मर्ज सॉर्ट लगभग 50 गुना कम काम करता है, पर अतिरिक्त मेमोरी लेता है।
आम गलतियाँ
- सिर्फ एक कंप्यूटर पर स्टॉपवॉच से गति नापना। इसकी जगह n के हिसाब से कदम गिनो।
- बिना छँटी सूची पर बाइनरी सर्च चलाना। इसकी प्रीकंडीशन है: सूची छँटी हो।
- बिग O में स्थिरांक रखना, जैसे O(2n) लिखना। यह बस O(n) है।
- ऐसा रिकर्सिव फ़ंक्शन लिखना जिसमें बेस केस न हो, या जो सवाल छोटा न करे।