Big-O से जटिलता मापना
हम एल्गोरिदम को सेकंड में नहीं नापते, क्योंकि कंप्यूटर अलग-अलग होते हैं। हम कदम गिनते हैं और देखते हैं कि इनपुट आकार n के साथ गिनती कैसे बढ़ती है। Big-O सिर्फ़ सबसे तेज़ बढ़ने वाला हिस्सा रखता है: 3n² + 5n + 7 = O(n²)।
| Big-O | नाम | उदाहरण |
|---|---|---|
| O(1) | स्थिर | सूची की पहली चीज़ पढ़ना |
| O(log n) | लघुगणकीय | बाइनरी सर्च |
| O(n) | रैखिक | लीनियर सर्च |
| O(n log n) | — | मर्ज सॉर्ट |
| O(n²) | द्विघाती | बबल सॉर्ट |
| O(2ⁿ) | घातीय | हर उपसमुच्चय आज़माना |
| O(n!) | क्रमगुणित | हर क्रम (रास्ता) आज़माना |
स्पेस जटिलता बताती है कि n के साथ मेमोरी कितनी बढ़ती है।
बहुपद बनाम घातीय: ट्रैक्टेबल और इंट्रैक्टेबल
अगर किसी समस्या का एल्गोरिदम बहुपद समय O(nᵏ) में चलता है, तो वह ट्रैक्टेबल है। अगर हर ज्ञात एल्गोरिदम इससे ज़्यादा समय लेता है, जैसे O(2ⁿ) या O(n!), तो वह इंट्रैक्टेबल है।
फ़र्क़ क्यों? n दोगुना करने पर n² चार गुना होता है। पर n में सिर्फ़ 1 जोड़ने से 2ⁿ दोगुना हो जाता है। 10⁹ कदम प्रति सेकंड पर n = 60 के 2ⁿ कदमों में लगभग 36 साल लगेंगे।
इंट्रैक्टेबल समस्याओं के लिए ह्यूरिस्टिक (अनुभव-आधारित नियम) अपनाते हैं, जैसे 'हमेशा सबसे पास वाले शहर जाओ'।
मशहूर कठिन समस्याएँ, P और NP
- ट्रैवलिंग सेल्समैन: n शहरों का सबसे छोटा चक्कर। सब आज़माने पर (n−1)!/2 रास्ते।
- नैपसैक: थैले में समाने वाली सबसे क़ीमती चीज़ें चुनना।
- टाइमटेबल / ग्राफ़ कलरिंग: परीक्षाओं को ऐसे समय देना कि किसी छात्र की टक्कर न हो।
P = वे समस्याएँ जो बहुपद समय में हल होती हैं। NP = वे जिनके उत्तर बहुपद समय में जाँचे जा सकते हैं। क्या P = NP? यह कंप्यूटर विज्ञान का सबसे बड़ा खुला सवाल है।
संगणनीय और असंगणनीय: हॉल्टिंग समस्या
अगर कोई एल्गोरिदम सीमित कदमों में हमेशा सही उत्तर दे, तो समस्या संगणनीय है। कुछ समस्याएँ असंगणनीय हैं: कोई एल्गोरिदम हर इनपुट पर उन्हें हल नहीं कर सकता।
हॉल्टिंग समस्या: कोई भी प्रोग्राम और इनपुट दिया हो, वह रुकेगा या हमेशा चलेगा? एलन ट्यूरिंग ने 1936 में दिखाया कि कोई सामान्य मशीन H यह नहीं बता सकती। सबूत का विचार: मान लो H है। एक प्रोग्राम X बनाओ जो H से अपने बारे में पूछे और उलटा करे (H कहे 'रुकेगा' तो लूप में चला जाए, H कहे 'नहीं रुकेगा' तो रुक जाए)। तब H, X के बारे में ग़लत होगी। इसलिए H बन ही नहीं सकती।
सीख: कुछ सीमाएँ गति की नहीं हैं। अनंत तेज़ कंप्यूटर भी असंगणनीय समस्या हल नहीं कर सकता।
करके देखो: विस्फोट महसूस करो
A, B, C लिखो। हर क्रम लिखो (ABC, ACB, …): 6 क्रम। D जोड़ो: 24। E जोड़ो: 120। हर नया अक्षर काम को गुणा कर देता है। यही n! वृद्धि है, जिससे रास्ता ढूँढना कठिन होता है।
मुख्य सूत्र और परिभाषाएँ
- Big-O सबसे तेज़ बढ़ने वाला पद रखता है: 4n² + 3n + 1 → O(n²)
- बहुपद समय: O(nᵏ) (ट्रैक्टेबल)
- घातीय: O(2ⁿ); क्रमगुणित: O(n!) (इंट्रैक्टेबल)
- n शहरों के चक्कर: (n − 1)!/2
- समय ≈ कदम ÷ (कदम प्रति सेकंड)
हल किए गए उदाहरण
1. 5n³ + 2n² + 100 का Big-O?
सबसे तेज़ पद रखो, स्थिरांक हटाओ: O(n³)।
2. O(n²) एल्गोरिदम n = 1000 पर 1 s लेता है। n = 3000 पर?
n तीन गुना, समय 3² = 9 गुना: लगभग 9 s।
3. O(2ⁿ) एल्गोरिदम n = 30 पर 1 s लेता है। n = 40 पर?
10 चीज़ें ज़्यादा → 2¹⁰ = 1024 गुना: लगभग 17 मिनट।
4. 5 शहरों के कितने चक्कर?
(5 − 1)!/2 = 24/2 = 12।
5. 10⁹ कदम/सेकंड पर 2⁵⁰ कदम कितने समय में?
2⁵⁰ ≈ 1.13 × 10¹⁵; समय ≈ 1.13 × 10⁶ s ≈ 13 दिन।
6. 'सूची सॉर्ट करना' ट्रैक्टेबल है? '500 छात्रों का सबसे अच्छा परीक्षा टाइमटेबल'?
सॉर्टिंग O(n log n), बहुपद, इसलिए ट्रैक्टेबल। सबसे अच्छे टाइमटेबल का कोई ज्ञात बहुपद एल्गोरिदम नहीं, इसलिए इंट्रैक्टेबल माना जाता है; स्कूल ह्यूरिस्टिक अपनाते हैं।
आम गलतियाँ
- सोचना कि तेज़ कंप्यूटर घातीय एल्गोरिदम ठीक कर देगा: वह बस कुछ चीज़ें और जोड़ने देता है।
- इंट्रैक्टेबल (बहुत धीमा) और असंगणनीय (असंभव) को एक समझना।
- Big-O में स्थिरांक रखना, जैसे O(3n²); सही है O(n²)।
- NP को 'नॉट पॉलिनोमियल' समझना। NP = उत्तर बहुपद समय में जाँचा जा सके।