कार्यान्वयन समस्याएँ
एल्गोरिद्म और डेटा स्ट्रक्चर्स (Algorithms and Data Structures) के साथ काम करते समय, कई बार लोगों को गलतफ़हमी होती है कि ये बहुत जटिल होते हैं। लेकिन ज़्यादातर मामलों में, ये बेहद सरल और सहज जान पड़ते हैं। इन्हें अच्छी तरह से समझने के लिए बस कुछ अभ्यास और व्यावहारिक अनुभव की ज़रूरत होती है ताकि पता चल सके कि ये एल्गोरिद्म वास्तव में कैसे काम करते हैं।
जब आप अलग-अलग समस्याओं और अभ्यासों पर काम करते हैं, तो जल्द ही महसूस होता है कि कुछ समस्याओं या सवालों के समूह एक जैसी विशेषताएँ साझा करते हैं। इन्हें अक्सर एक ही श्रेणी या समूह में रखा जा सकता है, और फिर उन्हीं तकनीकों का इस्तेमाल उस पूरे समूह की समस्याओं पर किया जा सकता है।
इनमें से एक महत्वपूर्ण समूह है “कार्यान्वयन समस्याएँ” (Implementation problems)। इन समस्याओं में आम तौर पर हल तक पहुँचने के चरण, समस्या विवरण में ही दिए होते हैं। यानी, प्रोग्राम को जिन क्रियाओं का पालन करना है, वे पहले से बताई गई होती हैं। एक सॉफ्टवेयर इंजीनियर के रूप में आपका काम होता है इन चरणों को सही और कुशल तरीके से अमल में लाना ताकि वांछित परिणाम प्राप्त हो सके। ध्यान देने की बात यह है कि भले ही समस्याओं में सारे चरण लिखे हों, उन्हें तुरंत और सीधे-सीधे लागू करना हमेशा आसान नहीं होता।
Challenge - Find the missing number
1 से लेकर n तक के सभी संख्याओं में से एक संख्या गायब है। आपका काम है उस गायब संख्या को ढूँढना।
इनपुट
The first line of the input contains a single integer
n (2 ≤ n ≤ 100 000).The second line of the input contains
n-1 space-separated integers (1 ≤ ≤ n).आउटपुट
The program should print the missing number.
Examples
Input | Output |
4
3 4 1 | 2 |
3
2 1 | 3 |
Tutorial on Complexity and Big Notation
ऊपर बताई गई समस्या पहली नज़र में आसान लग सकती है, लेकिन इसका एक साधारण (naive) हल इतना तेज़ नहीं होगा कि वह सारे टेस्ट केस पूरे कर पाए।
एक साधारण तरीका यह हो सकता है कि आप इनपुट से सभी तत्वों को एक लिस्ट में पढ़ लें और फिर 1 से n तक प्रत्येक संख्या के लिए जाँचें कि क्या वह लिस्ट में मौजूद है। जिस संख्या के लिए “नहीं मिलती” का जवाब मिले, वही गायब संख्या होगी:
n = int(input())
a = [int(ai) for ai in input().split()]
for i in range(1, n + 1): # n operations
if i not in a: # n operations (goes through all the elements)
print(i) # We found the solution!लेकिन यह एल्गोरिद्म काफ़ी धीमा हो जाता है। यह 1 से n तक हर संख्या के लिए लिस्ट में खोज करता है। लिस्ट में खोज एक रैखिक ऑपरेशन (linear operation) है, जिसका मतलब है कि लिस्ट के हर तत्व को जाँचना होता है, और लिस्ट की लंबाई लगभग
n ही है (ठीक n-1, पर इससे ज़्यादा फर्क़ नहीं पड़ता)।इस तरह यह एल्गोरिद्म लगभग ऑपरेशन्स करता है: बाहरी लूप n बार चलता है और हर बार लिस्ट में खोज भी
n ऑपरेशन्स के आसपास लगाती है। नतीजतन, कुल मिलाकर लगभग कार्य-चक्र (operations) लगते हैं।💻
हमारे कम्प्यूटर आम तौर पर एक सेकंड में लगभग 10 से 100 मिलियन ऑपरेशन्स कर सकते हैं। यदि किसी समस्या के लिए समय सीमा 1 सेकंड है (जो एल्गोरिद्म समस्याओं में एक आम समय सीमा होती है), तो कोशिश यह रहती है कि कुल मिलाकर 100 मिलियन से अधिक ऑपरेशन्स न करने पड़ें।
उदाहरण के लिए, ऊपर की समस्या में
n अधिकतम 100 000 तक हो सकता है। इस स्थिति में (10 बिलियन) ऑपरेशन्स हो जाएँगे, जिसे सामान्य कम्प्यूटर पर पूरा होने में क़रीब 100 सेकंड लग सकते हैं; जबकि समस्या की समय सीमा 1 सेकंड मात्र हो सकती है। इसलिए हमें एक अधिक कुशल हल की ज़रूरत पड़ती है।Big Notation
Big O (बिग ओ) नोटेशन एक गणितीय अभिव्यक्ति है, जो किसी एल्गोरिद्म के समय जटिलता (time complexity) के ऊपरी आयाम को बताती है—जैसे-जैसे इनपुट का आकार बढ़ता है, एल्गोरिद्म का संचालन कितनी तेज़ी से बढ़ेगा, इसका अंदाज़ा Big O नोटेशन से लगाया जाता है।
ऊपर हमने गणना की कि साधारण हल में लगभग ऑपरेशन्स लग रहे हैं, इसलिए हम कह सकते हैं कि उस हल की जटिलता है।
आगे के अध्यायों में हम इस विषय पर और विस्तार से चर्चा करेंगे, ताकि आपको इससे जुड़ी अवधारणाएँ और औपचारिकताएँ और ज़्यादा स्पष्ट हो सकें।
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB