1.आसान
सॉर्टेड ऐरे पर बाइनरी सर्च (binary search) की टाइम कॉम्प्लेक्सिटी क्या है?
- AO(n log n)
- BO(1)
- CO(n)
- DO(log n)
उत्तरों सहित एल्गोरिदम और जटिलता वर्कशीट
2.आसान
किसी एल्गोरिदम का वर्स्ट-केस रनिंग टाइम क्या बताता है?
- An आकार के सभी इनपुट पर लगने वाला अधिकतम समय
- Bसबसे छोटे इनपुट पर लगने वाला समय
- Cआकार n के किसी यादृच्छिक इनपुट पर लगने वाला अपेक्षित समय
- Dधीमे कंप्यूटर पर लगने वाला समय
3.आसान
बाइनरी सर्च को अपने इनपुट से क्या चाहिए?
- Aऐरे सॉर्टेड होना चाहिए
- Bऐरे में 1000 से अधिक तत्व नहीं होने चाहिए
- Cऐरे की लंबाई दो की घात होनी चाहिए
- Dऐरे में केवल धनात्मक संख्याएँ होनी चाहिए
4.मध्यम
रिकरेंस T(n) = T(n − 1) + O(n) का हल क्या है?
- AO(n)
- BO(n log n)
- CO(n²)
- DO(2ⁿ)
5.मध्यम
रिकरेंस T(n) = 2T(n/2) + O(1) का हल क्या है?
- AO(log n)
- BO(n log n)
- CO(n)
- DO(n²)
6.मध्यम
बॉटम-अप तालिका से n-वीं फ़िबोनाची संख्या की गणना की टाइम कॉम्प्लेक्सिटी क्या है?
- AO(n²)
- BO(n)
- CO(2ⁿ)
- DO(log n)
7.कठिन
सिंगली लिंक्ड लिस्ट पर बाइनरी सर्च O(log n) समय क्यों नहीं देती?
- Aलिंक्ड लिस्ट सॉर्ट नहीं की जा सकतीं
- Bबाइनरी सर्च को कम से कम दोगुनी मेमोरी चाहिए
- Cलिंक्ड लिस्ट नोड पर तुलनाएँ धीमी होती हैं
- Dबीच के तत्व तक पहुँचने में O(n) चरण लगते हैं, क्योंकि सीधी इंडेक्स पहुँच नहीं है
8.कठिन
केवल अंतिम दो मान रखने वाले लूप से n-वीं फ़िबोनाची संख्या की गणना की समय और स्पेस लागत क्या है?
- AO(n) समय और O(n) स्पेस
- BO(log n) समय और O(n) स्पेस
- CO(n) समय और O(1) स्पेस
- DO(2ⁿ) समय और O(1) स्पेस
उत्तर कुंजी
- 1. D · O(log n)
- 2. A · n आकार के सभी इनपुट पर लगने वाला अधिकतम समय
- 3. A · ऐरे सॉर्टेड होना चाहिए
- 4. C · O(n²)
- 5. C · O(n)
- 6. B · O(n)
- 7. D · बीच के तत्व तक पहुँचने में O(n) चरण लगते हैं, क्योंकि सीधी इंडेक्स पहुँच नहीं है
- 8. C · O(n) समय और O(1) स्पेस
पूरे चरण-दर-चरण हल: इस विषय का अभ्यास examproblems.com पर करें।