1.आसान
एवरेज-केस रनिंग टाइम क्या बताता है?
- Aबेस्ट-केस और वर्स्ट-केस रनिंग टाइम के बीच का मध्य मान
- Bऔसत लंबाई वाले इनपुट का समय
- Cसबसे आम कंप्यूटर पर समय
- Dn आकार के इनपुट के किसी दिए गए वितरण पर अपेक्षित समय
उत्तरों सहित एल्गोरिदम और जटिलता वर्कशीट
2.आसान
कौन-सा नोटेशन वृद्धि की ऊपरी सीमा (upper bound) को दर्शाता है?
- ALittle omega
- BBig Theta
- CBig O
- DBig Omega
3.आसान
ब्रूट-फ़ोर्स एल्गोरिदम क्या है?
- Aवह जो कई प्रोसेसरों पर चलता है
- Bवह जो सभी संभावित उम्मीदवार समाधान आज़माता है
- Cवह जो यादृच्छिक रूप से उत्तर का अनुमान लगाता है
- Dवह जो हमेशा रिकर्शन का उपयोग करता है
4.मध्यम
रिकरेंस T(n) = T(n/2) + O(1) का हल क्या है?
- AO(1)
- BO(n)
- CO(log n)
- DO(n log n)
5.मध्यम
मानक तीन लूप से दो n × n मैट्रिक्स गुणा करने की टाइम कॉम्प्लेक्सिटी क्या है?
- AO(n³)
- BO(n² log n)
- CO(n²)
- DO(n)
6.मध्यम
आधार k में d अंकों वाले n पूर्णांकों पर LSD रेडिक्स सॉर्ट का रनिंग टाइम क्या है?
- AO(n log n)
- BO(d(n + k))
- CO(dn log k)
- DO(n²)
7.कठिन
डायनेमिक प्रोग्रामिंग से हल की गई 0/1 नैपसैक (knapsack) समस्या में O(nW) समय लगता है। इसे स्यूडो-पॉलिनोमियल (pseudo-polynomial) क्यों कहा जाता है?
- AW एक संख्या है, इसलिए समय W को लिखने में प्रयुक्त बिट्स की संख्या में घातांकी है
- Bक्योंकि n हमेशा छोटा होता है
- Cक्योंकि एल्गोरिदम यादृच्छिक (randomised) है और उसका रनिंग टाइम हर इनपुट के साथ बदलता है
- Dक्योंकि यह केवल W = 0 के लिए काम करता है
8.कठिन
इनमें से कौन-सी संतुष्टि समस्या बहुपदी समय में हल होने योग्य ज्ञात है?
- Aकंजंक्टिव नॉर्मल फ़ॉर्म में सूत्रों पर सामान्य SAT
- B2-SAT, जिसमें हर क्लॉज़ में अधिकतम दो लिटरल होते हैं
- C3-SAT, जिसमें हर क्लॉज़ में ठीक तीन लिटरल होते हैं
- Dसर्किट संतुष्टि
उत्तर कुंजी
- 1. D · n आकार के इनपुट के किसी दिए गए वितरण पर अपेक्षित समय
- 2. C · Big O
- 3. B · वह जो सभी संभावित उम्मीदवार समाधान आज़माता है
- 4. C · O(log n)
- 5. A · O(n³)
- 6. B · O(d(n + k))
- 7. A · W एक संख्या है, इसलिए समय W को लिखने में प्रयुक्त बिट्स की संख्या में घातांकी है
- 8. B · 2-SAT, जिसमें हर क्लॉज़ में अधिकतम दो लिटरल होते हैं
पूरे चरण-दर-चरण हल: इस विषय का अभ्यास examproblems.com पर करें।