1.आसान
ऐरे में इंडेक्स द्वारा किसी तत्व तक पहुँचने में कितना समय लगता है?
- AO(log n)
- BO(1)
- CO(n²)
- DO(n)
उत्तरों सहित एल्गोरिदम और जटिलता वर्कशीट
2.आसान
मर्ज सॉर्ट की वर्स्ट-केस टाइम कॉम्प्लेक्सिटी क्या है?
- AO(log n)
- BO(n log n)
- CO(n²)
- DO(n)
3.आसान
एक O(n) एल्गोरिदम n = 10 लाख के लिए 3 सेकंड लेता है। n = 20 लाख के लिए लगभग कितना समय लगेगा?
- A12 सेकंड
- B6 सेकंड
- C3 सेकंड
- D9 सेकंड
4.मध्यम
रिकरेंस T(n) = T(n − 1) + O(1) का हल क्या है?
- AO(2ⁿ)
- BO(n²)
- CO(n)
- DO(log n)
5.मध्यम
क्विकसॉर्ट हमेशा पहले तत्व को पिवट के रूप में उपयोग करता है। किस इनपुट पर यह अपना वर्स्ट-केस व्यवहार दिखाता है?
- Aलंबाई 2 का ऐरे
- Bयादृच्छिक क्रम वाला ऐरे
- Cऐसा ऐरे जिसके सभी तत्व भिन्न हैं
- Dएक ऐरे जो पहले से सॉर्टेड है
6.मध्यम
डायनेमिक प्रोग्रामिंग (dynamic programming) तब उपयोगी है जब किसी समस्या में हों:
- Aकेवल यादृच्छिक इनपुट
- Bकेवल एक लूप
- Cओवरलैपिंग उप-समस्याएँ और इष्टतम उप-संरचना (optimal substructure)
- Dकोई उप-समस्या बिल्कुल न हो, ताकि उसे एक ही चरण में हल किया जा सके
7.कठिन
कौन-सा एल्गोरिदम बार-बार ऐसा सबसे सस्ता एज जोड़कर, जो चक्र न बनाए, मिनिमम स्पैनिंग ट्री खोजता है?
- AKruskal का एल्गोरिदम
- BDijkstra का एल्गोरिदम
- CFloyd–Warshall
- Dएक नोड से शुरू होने वाला Prim का एल्गोरिदम
8.कठिन
कोई समस्या NP-complete होती है यदि वह:
- Aहल करना असंभव है
- BNP में है और हर NP समस्या बहुपद समय में उसमें रिड्यूस होती है
- Cबहुपद समय में हल की जा सकती है
- DNP से बाहर है लेकिन सभी NP समस्याओं से कठिन है, जैसे हॉल्टिंग समस्या
उत्तर कुंजी
- 1. B · O(1)
- 2. B · O(n log n)
- 3. B · 6 सेकंड
- 4. C · O(n)
- 5. D · एक ऐरे जो पहले से सॉर्टेड है
- 6. C · ओवरलैपिंग उप-समस्याएँ और इष्टतम उप-संरचना (optimal substructure)
- 7. A · Kruskal का एल्गोरिदम
- 8. B · NP में है और हर NP समस्या बहुपद समय में उसमें रिड्यूस होती है
पूरे चरण-दर-चरण हल: इस विषय का अभ्यास examproblems.com पर करें।