1.आसान
n बड़ा होने पर इनमें से कौन सबसे धीमा बढ़ता है?
- AO(n²)
- BO(n log n)
- CO(log n)
- DO(n)
उत्तरों सहित एल्गोरिदम और जटिलता वर्कशीट
2.आसान
एडजेसेंसी लिस्ट (adjacency list) के रूप में संग्रहीत ग्राफ़ पर डेप्थ-फ़र्स्ट सर्च (DFS) की टाइम कॉम्प्लेक्सिटी क्या है?
- AO(V + E)
- BO(E log V)
- CO(V²)
- DO(V × E)
3.आसान
यदि कोई ऑपरेशन O(1) समय में चलता है, तो इसका क्या अर्थ है?
- Aउसका रनिंग टाइम इनपुट आकार के साथ नहीं बढ़ता
- Bवह रनिंग टाइम के प्रति सेकंड ठीक एक तत्व संसाधित करता है
- Cउसमें हमेशा ठीक एक सेकंड लगता है
- Dउसे केवल एक बार चलाया जा सकता है
4.मध्यम
V शीर्षों और E किनारों वाले ग्राफ़ पर बेलमैन–फ़ोर्ड एल्गोरिदम की टाइम कॉम्प्लेक्सिटी क्या है?
- AO(V³ × E)
- BO(V + E)
- CO(E log V)
- DO(V × E)
5.मध्यम
एक सॉर्टेड ऐरे में आप दोनों सिरों से एक-एक पॉइंटर को भीतर की ओर खिसकाते हुए ऐसे दो तत्व खोजते हैं जिनका योग लक्ष्य के बराबर हो। टाइम कॉम्प्लेक्सिटी क्या है?
- AO(n²)
- BO(n)
- CO(log n)
- DO(n log n)
6.मध्यम
गैर-ऋणात्मक एज वेट वाले ग्राफ़ में एक स्रोत से सबसे छोटे पथ कौन-सा एल्गोरिदम खोजता है?
- Aडेप्थ-फ़र्स्ट सर्च (DFS)
- Bहर स्थिति में Bellman–Ford आवश्यक है
- CKruskal का एल्गोरिदम
- DDijkstra का एल्गोरिदम
7.कठिन
बॉटम-अप विधि से n अनसॉर्टेड तत्वों से बाइनरी हीप बनाने की टाइम कॉम्प्लेक्सिटी क्या है?
- AO(n log n)
- BO(n²)
- CO(log n)
- DO(n)
8.कठिन
यदि कोई किसी एक NP-complete समस्या के लिए बहुपदी-समय एल्गोरिदम खोज ले, तो क्या निष्कर्ष निकलेगा?
- ANP की हर समस्या बहुपदी समय में हल हो सकेगी, इसलिए P = NP
- Bकेवल वही एक समस्या P में चली जाएगी
- Cसभी घातांकी-समय एल्गोरिदम तुरंत रैखिक समय में चलने लगेंगे
- Dहॉल्टिंग समस्या निर्णेय हो जाएगी
उत्तर कुंजी
- 1. C · O(log n)
- 2. A · O(V + E)
- 3. A · उसका रनिंग टाइम इनपुट आकार के साथ नहीं बढ़ता
- 4. D · O(V × E)
- 5. B · O(n)
- 6. D · Dijkstra का एल्गोरिदम
- 7. D · O(n)
- 8. A · NP की हर समस्या बहुपदी समय में हल हो सकेगी, इसलिए P = NP
पूरे चरण-दर-चरण हल: इस विषय का अभ्यास examproblems.com पर करें।