1.आसान
एक O(n²) एल्गोरिदम n = 1000 के लिए 1 सेकंड लेता है। n = 2000 के लिए लगभग कितना समय लगेगा?
- A8 सेकंड
- B1 सेकंड
- C2 सेकंड
- D4 सेकंड
उत्तरों सहित एल्गोरिदम और जटिलता वर्कशीट
2.आसान
किसी समस्या को सामान्यतः सुसाध्य (tractable) कब कहा जाता है?
- Aजब उसे केवल हर संभावना आज़माकर हल किया जा सके
- Bजब उसे स्थिर समय में हल किया जा सके
- Cजब उसका कोई समाधान न हो
- Dजब उसे बहुपदी समय में हल किया जा सके
3.आसान
एवरेज-केस रनिंग टाइम क्या बताता है?
- Aबेस्ट-केस और वर्स्ट-केस रनिंग टाइम के बीच का मध्य मान
- Bn आकार के इनपुट के किसी दिए गए वितरण पर अपेक्षित समय
- Cसबसे आम कंप्यूटर पर समय
- Dऔसत लंबाई वाले इनपुट का समय
4.मध्यम
किसी समस्या में इष्टतम उप-संरचना (optimal substructure) होने का क्या अर्थ है?
- Aसमस्या का ठीक एक इष्टतम समाधान है, जो हर उप-समस्या में साझा होता है
- Bसमस्या को स्थिर समय में हल किया जा सकता है
- Cहर उप-समस्या का आकार समान है
- Dएक इष्टतम समाधान उसकी उप-समस्याओं के इष्टतम समाधानों से बनाया जा सकता है
5.मध्यम
एक ग्रीडी एल्गोरिदम (greedy algorithm):
- Aकेवल रिकर्शन का उपयोग करता है
- Bहर संभव समाधान आज़माता है
- Cहर चरण में स्थानीय रूप से सर्वोत्तम विकल्प चुनता है
- Dहमेशा इष्टतम समाधान देता है
6.मध्यम
मर्ज सॉर्ट के लिए डायनेमिक प्रोग्रामिंग कोई वास्तविक गति-वृद्धि क्यों नहीं देती?
- Aइसकी उप-समस्याएँ अतिव्यापी नहीं हैं, इसलिए दोबारा उपयोग करने को कुछ नहीं है
- Bडायनेमिक प्रोग्रामिंग केवल ग्राफ़ समस्याओं पर काम करती है, ऐरे पर नहीं
- Cमर्ज सॉर्ट पहले से ही O(n) है
- Dमर्ज सॉर्ट की कोई रिकर्सिव संरचना नहीं है
7.कठिन
सॉर्टेड ऐरे में किसी भी तुलना-आधारित खोज को वर्स्ट केस में Ω(log n) तुलनाएँ क्यों चाहिए?
- An संभावित परिणामों वाले निर्णय वृक्ष (decision tree) की गहराई कम से कम log₂ n होनी चाहिए
- Bहर तुलना में लघुगणकीय समय लगता है
- Cबाइनरी सर्च ही एकमात्र संभव एल्गोरिदम है, और उसे log₂ n तुलनाएँ चाहिए
- Dहर तत्व की कम से कम एक बार तुलना होनी चाहिए
8.कठिन
little-o नोटेशन के बारे में कौन-सा कथन सही है?
- A2n = o(n), क्योंकि 2n धीरे बढ़ता है
- Bn = o(n²), पर n, o(n) नहीं है
- Cn = o(n), क्योंकि हर फलन स्वयं का little-o है
- Dn² = o(n)
उत्तर कुंजी
- 1. D · 4 सेकंड
- 2. D · जब उसे बहुपदी समय में हल किया जा सके
- 3. B · n आकार के इनपुट के किसी दिए गए वितरण पर अपेक्षित समय
- 4. D · एक इष्टतम समाधान उसकी उप-समस्याओं के इष्टतम समाधानों से बनाया जा सकता है
- 5. C · हर चरण में स्थानीय रूप से सर्वोत्तम विकल्प चुनता है
- 6. A · इसकी उप-समस्याएँ अतिव्यापी नहीं हैं, इसलिए दोबारा उपयोग करने को कुछ नहीं है
- 7. A · n संभावित परिणामों वाले निर्णय वृक्ष (decision tree) की गहराई कम से कम log₂ n होनी चाहिए
- 8. B · n = o(n²), पर n, o(n) नहीं है
पूरे चरण-दर-चरण हल: इस विषय का अभ्यास examproblems.com पर करें।