1.आसान
कौन-सा नोटेशन वृद्धि की ऊपरी सीमा (upper bound) को दर्शाता है?
- ABig Theta
- BBig Omega
- CBig O
- DLittle omega
उत्तरों सहित एल्गोरिदम और जटिलता वर्कशीट
2.आसान
सॉर्टेड ऐरे पर बाइनरी सर्च (binary search) की टाइम कॉम्प्लेक्सिटी क्या है?
- AO(n log n)
- BO(1)
- CO(n)
- DO(log n)
3.आसान
मेमोइज़ेशन (memoisation) क्या है?
- Aफ़ंक्शन कॉल के परिणाम संग्रहीत करना ताकि दोहराई गई कॉल का उत्तर मेमोरी से मिले
- Bफ़ंक्शन लौटने के बाद मेमोरी मुक्त करना
- Cरिकर्शन को अपने आप समतुल्य लूप में बदलना ताकि कॉल स्टैक की आवश्यकता न रहे
- Dकोड की हर पंक्ति के आगे टिप्पणियाँ लिखना
4.मध्यम
रिकरेंस T(n) = 2T(n/2) + O(n) का हल क्या है?
- AO(log n)
- BO(n log n)
- CO(n²)
- DO(n)
5.मध्यम
आधार k में d अंकों वाले n पूर्णांकों पर LSD रेडिक्स सॉर्ट का रनिंग टाइम क्या है?
- AO(dn log k)
- BO(n²)
- CO(n log n)
- DO(d(n + k))
6.मध्यम
Big O में, जैसे O(log n) में, लघुगणक का आधार सामान्यतः क्यों छोड़ दिया जाता है?
- Aकंप्यूटर विज्ञान में सभी लघुगणकों का आधार 10 होता है, इसलिए वह निहित है
- Bआधार केवल छोटे n के लिए मायने रखता है
- Cभिन्न आधारों वाले लघुगणक केवल एक स्थिर गुणक से भिन्न होते हैं
- Dलघुगणक हमेशा पूर्णांकों में पूर्णांकित किए जाते हैं
7.कठिन
सिंगली लिंक्ड लिस्ट पर बाइनरी सर्च O(log n) समय क्यों नहीं देती?
- Aबाइनरी सर्च को कम से कम दोगुनी मेमोरी चाहिए
- Bलिंक्ड लिस्ट नोड पर तुलनाएँ धीमी होती हैं
- Cलिंक्ड लिस्ट सॉर्ट नहीं की जा सकतीं
- Dबीच के तत्व तक पहुँचने में O(n) चरण लगते हैं, क्योंकि सीधी इंडेक्स पहुँच नहीं है
8.कठिन
कौन-सी तकनीक किसी भी इनपुट पर क्विकसॉर्ट को अपेक्षित (expected) O(n log n) रनिंग टाइम देती है?
- Aक्विकसॉर्ट चलाने से पहले इनपुट को सॉर्ट करना
- Bहमेशा पहला तत्व चुनना
- Cकेवल बाईं ओर रिकर्शन का उपयोग करना
- Dपिवट को समान रूप से यादृच्छिक (uniformly at random) चुनना
उत्तर कुंजी
- 1. C · Big O
- 2. D · O(log n)
- 3. A · फ़ंक्शन कॉल के परिणाम संग्रहीत करना ताकि दोहराई गई कॉल का उत्तर मेमोरी से मिले
- 4. B · O(n log n)
- 5. D · O(d(n + k))
- 6. C · भिन्न आधारों वाले लघुगणक केवल एक स्थिर गुणक से भिन्न होते हैं
- 7. D · बीच के तत्व तक पहुँचने में O(n) चरण लगते हैं, क्योंकि सीधी इंडेक्स पहुँच नहीं है
- 8. D · पिवट को समान रूप से यादृच्छिक (uniformly at random) चुनना
पूरे चरण-दर-चरण हल: इस विषय का अभ्यास examproblems.com पर करें।