Asymptotic Worst Case Time and Time Complexity MCQ Quiz in हिन्दी - Objective Question with Answer for Asymptotic Worst Case Time and Time Complexity - मुफ्त [PDF] डाउनलोड करें

सही उत्तर (A) - (III), (B) - (I), (C) - (II), (D) - (IV) है।

• A (बेलमैन- फोर्ड एल्गोरिदम) → III (O(nm))
• B (दिजक्स्त्रा एल्गोरिदम) → I (O(|V|²))
• C (प्रीम्स एल्गोरिदम) → II (O((V + E) log V))
• D (टोपोलॉजिकल सोर्टिंग) → IV (O(n + m))

Key Points

1. बेलमैन- फोर्ड एल्गोरिदम → O(nm) |V| - 1 बार E किनारों पर पुनरावृति करता है, जिससे O(VE) मिलता है, जो घने ग्राफ़ में O(nm) है।

2. दिजक्स्त्रा एल्गोरिदम → O(|V|²) अडजैसेन्सी मैट्रिक्स का उपयोग करते हुए, यह सभी शीर्षों को स्कैन करता है, जिससे O(V²) समय जटिलता प्राप्त होती है।

3. प्रीम्स एल्गोरिदम → O((V + E) log V) आसन्नता सूची के साथ प्रायोरिटी क्यू (मिन-हीप) का उपयोग करता है, जिससे O((V + E) log V) मिलता है।

4. टोपोलोजीकल सोर्टिंग→ O(n + m) DFS या Kahn के एल्गोरिथम का उपयोग करता है, V शीर्षों और E किनारों पर पुनरावृति करता है, जिसके परिणामस्वरूप O(V + E) होता है।

Important Points

• बेलमैन- फोर्ड एल्गोरिथम का उपयोग भारित ग्राफ़ में एकल स्रोत शीर्ष से अन्य सभी शीर्षों तक सबसे छोटे पथ खोजने के लिए किया जाता है।
• दिजक्स्त्रा एल्गोरिथम भी भारित ग्राफ़ में सबसे छोटा पथ खोजने के लिए उपयोग किया जाता है, लेकिन यह ऋणात्मक भार वाले किनारों के साथ काम नहीं करता है।
• प्रीम्स एल्गोरिथम भारित ग्राफ़ के न्यूनतम फैलाव वृक्ष को खोजने के लिए उपयोग किया जाता है।
• टोपोलॉजिकल सॉर्टिंग का उपयोग निर्देशित असाइक्लिक ग्राफ़ (DAG) के शीर्षों को क्रमबद्ध करने के लिए किया जाता है।

Additional Information

• बेलमैन- फोर्ड एल्गोरिथम ऋणात्मक भारों को संभाल सकता है, जबकि दिजक्स्त्रा एल्गोरिथम नहीं।
• प्रीम्स एल्गोरिथम और दिजक्स्त्रा एल्गोरिथम में समान संरचनाएँ हैं, लेकिन वे अलग-अलग समस्याओं का समाधान करते हैं।
• टोपोलॉजिकल सॉर्टिंग कार्य शेड्यूलिंग के लिए महत्वपूर्ण है, जैसे कि परियोजना प्रबंधन में।

सही उत्तर लघुतम पथ समस्या है।

Key Points

• लघुतम पथ समस्या NP-पूर्ण समस्या नहीं है। इसे डाइकस्ट्रा या बेलमैन-फोर्ड जैसे एल्गोरिथम का उपयोग करके बहुपद समय में हल किया जा सकता है।
• NP-पूर्ण समस्याएं समस्याओं का एक वर्ग हैं जो NP (गैर-निर्धारक बहुपद समय) और NP-कठिन दोनों हैं। यदि कोई NP-पूर्ण समस्या बहुपद समय में हल हो सकती है, तो NP में प्रत्येक समस्या को भी बहुपद समय में हल किया जा सकता है।

Additional Information

• ट्रैवलिंग सेल्समेन समस्या (TSP): यह एक NP-पूर्ण समस्या है जहाँ लक्ष्य सबसे छोटा संभव पथ खोजना है जो प्रत्येक शहर में ठीक एक बार जाता है और मूल शहर में वापस आता है।
• बूलियन संतुष्टि समस्या (SAT): यह पहली समस्या थी जिसे NP-पूर्ण सिद्ध किया गया था। इसमें यह निर्धारित करना शामिल है कि क्या कोई व्याख्या है जो दिए गए बूलियन सूत्र को संतुष्ट करती है।

Key Points

आरोही क्रम में एल्गोरिथम की जटिलता:

स्थिरांक O(c) < लघुगणक O(log n) < log-वर्ग O(log²n) < रैखिक O(n) < द्विघात O(n²) < घनीय O(n³) < घातांकीय (2ⁿ)

स्थिरांक < 1/n < log n < n < nlogn < n² < n³ < ... < 2ⁿ < 3ⁿ < 4ⁿ < ... < nⁿ 

आरोही क्रम में एल्गोरिथम की निम्नलिखित जटिलता। 

O(2n) घातांकीय

O(n) रैखिक 

O(log2 n) लघुगणक

O(n log2 n) रैखिक-लघुगणक

O(n2) द्विघात

अतः सही क्रम O(log2 n) < O(n) < O(n log2 n) < O(n2) < O(2n) है। 

मास्टर प्रमेय: T(n)= aT(n/b)+f(n); a>=1,b>1 है।

इसलिये a = 2, b = 2, f(n) = n

\(n^{log_ba} = n^{log_22}=n\)

\({f(n) = n^{log_ba}=n}\)

T (n) = 2T(n/2) + c

निम्न के साथ तुलना करना:

T(n) = aT(n/b) + nk × log2p n

a = 2, b = 2, k = 0, p = 0

bk = 2⁰ = 1

a > bk और p > -1

मास्टर प्रमेय द्वारा

T(n) = θ(n^log_ba ) 

T(n) = θ(nlog22) 

T(n) = θ(n) 

\({\rm{T}}\left( {\rm{n}} \right) = 2{\rm{T}}\left( {\frac{{\rm{n}}}{2}} \right) + \log {\rm{n}}\)

के साथ तुलना करने पर:

\({\rm{T}}\left( {\rm{n}} \right) = {\rm{aT}}\left( {\frac{{\rm{n}}}{{\rm{b}}}} \right) + f\left( n \right)\)

a = 2, b = 2, f(n) = log n

\({n^{{{\log }_2}2}} = n\) > f(n)

मास्टर के प्रमेय द्वारा

\(T\left( {\rm{n}} \right) = {\rm{O}}\left( {\rm{n}} \right)\)

हमें यह जांचना होगा कि यहां कितनी बार आंतरिक लूप निष्पादित किया जाएगा।

 i=1 के लिए,

j 1 + 2 + 3 + ………… (n बार) रन होगा

i=2 के लिए

j 1,3,5, 7, 9, 11, ……… .. (n/2 बार) रन होगा

i = 3 के लिए

j 1,4,7,10, 13 ………… (n/3 बार) रन होगा

इस प्रकार,

\(T\left( n \right) = n + \frac{n}{2} + \frac{n}{3} + \frac{n}{4} + \frac{n}{5} + \frac{n}{6} \ldots + \frac{n}{n}\)

\(= n\left( {1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} \ldots + \frac{1}{n}} \right)\;\)

तो, दिए गए प्रोग्राम की समय जटिलता = Θ (n log n)

सही उत्तर अंतरिक्ष दक्षता और समय दक्षता है।

Key Points

• कंप्यूटर विज्ञान में, एल्गोरिथम दक्षता एक एल्गोरिथ्म की एक संपत्ति है जो एल्गोरिथम द्वारा उपयोग किए जाने वाले कम्प्यूटेशनल संसाधनों की संख्या से संबंधित है।
• एक एल्गोरिथ्म का विश्लेषण उसके संसाधन उपयोग को निर्धारित करने के लिए किया जाना चाहिए, और एक एल्गोरिथ्म की दक्षता को विभिन्न संसाधनों के उपयोग के आधार पर मापा जा सकता है। 
• प्रदर्शन के लिए दो क्षेत्र महत्वपूर्ण हैं :
  • अंतरिक्ष दक्षता - एक एल्गोरिथ्म को निष्पादित करने के लिए आवश्यक मेमोरी की मात्रा का एक उपाय।
  • समय दक्षता - एक एल्गोरिथ्म को निष्पादित करने के लिए समय की मात्रा का एक उपाय।

Additional Information

 इसके अलावा, प्रत्येक एल्गोरिथ्म को निम्न मानदंडों को पूरा करना चाहिए:

• इनपुट: शून्य या अधिक मात्रा में हैं जो बाहरी रूप से आपूर्ति की जाती हैं;
• आउटपुट: कम से कम एक मात्रा में उत्पादन किया जाता है;
• निश्चितता: प्रत्येक निर्देश स्पष्ट और स्पष्ट होना चाहिए;
• परिमितता: यदि हम एक एल्गोरिथ्म के निर्देशों का पता लगाते हैं, तो सभी मामलों के लिए एल्गोरिथ्म एक सीमित संख्या में चरणों के बाद समाप्त हो जाएगा;
• प्रभावशीलता: प्रत्येक निर्देश को पर्याप्त रूप से बुनियादी होना चाहिए कि यह केवल पेंसिल और कागज का उपयोग करके किसी व्यक्ति द्वारा किया जा सकता है। यह पर्याप्त नहीं है कि प्रत्येक ऑपरेशन निश्चित है, लेकिन यह संभव भी होना चाहिए। 

दिए गए मान हैं: 10 (एक स्थिर मान)

√n (एक चर n का वर्गमूल जो कोई भी मान ले सकता है) n (एक चर) log2n (लघुगणक)

\(\frac{100}{n}\) (यह 100 को एक चर से विभाजित करता है)

जैसा कि हम जानते हैं कि स्पर्शोन्मुख जटिलता के मामले में स्थिरांक एक चर से छोटा होता है क्योंकि एक चर किसी भी मान को छोटा या बड़ा ले सकता है। लेकिन जब हम 10 की तुलना \(\frac{100}{n}\) से करते हैं, क्योंकि 100 n से विभाज्य है और यदि n अनंत में जाता है तो यह मान शून्य हो जाएगा। तो, \(\frac{100}{n}\) 10 से छोटा है।

log2n के मामले में वृद्धि दर लॉगरिदमिक है जो रैखिक वृद्धि से छोटा है।

√n और n के बीच तुलना। n के मामले में रैखिक वृद्धि, यह √n से बड़ी है।

तो, पूर्ण क्रम है: \(\frac{100}{n}\) < 10 < log2 n < √n < n

वैकल्पिक विधि:

n = 21024 लेना

10, \(2^{\frac{1024}{2}}\), \(\frac{100}{2^{1024}}\), log2(21024), 21024

10, 2512, \(\frac{100}{2^{1024}}\), 1024 × log22, 21024

10, 2512, \(\frac{100}{2^{1024}}\), 1024, 21024

बढ़ते क्रम के संदर्भ में:

100/(2 ¹⁰²⁴ ) < 10 <1024 <2 ⁵¹² <2 ¹⁰²⁴

सही उत्तर विकल्प 3 है।

व्याख्या:

पुनरावृत्ति संबंध: T(n) = 7T(n/7) + n

T(n) = aT(n/b) + θ(nk logpn) के साथ तुलना करना

a = 7, b = 7, k = 1, p = 0

मास्टर प्रमेय का उपयोग करना,

चूँकि  a = bk और p > -1,

T(n) = O(nlog(n))

• दिज्क्स्ट्रा एल्गोरिथ्म एक एल्गोरिथ्म है हे जो ग्राफ और समय जटिलता में नोड के बीच सबसे छोटे पथ को खोजने के लिए O(V​2) है।
• क्रुशल का एल्गोरिथ्म एक न्यूनतम विस्तारित ट्री एल्गोरिथ्म है जो कम से कम संभव वजन का एक छोर प्राप्त करता है फारेस्ट में किसी भी दो ट्री को जोड़ता है।
• एक निर्देशित ग्राफ का एक टोपोलॉजिकल सॉर्ट या टोपोलॉजिकल क्रम इसके शीर्ष का एक रैखिक क्रम है, जो कि प्रत्येक निर्देशित छोर uv  शीर्ष u से शीर्ष v के लिए होता है, u, v से पहले आता है।
• फ्लोयड-वॉरसॉल एल्गोरिथ्म एक एल्गोरिथ्म है जो धनात्मक या ऋणात्मक छोर भार के साथ एक भारित ग्राफ में सबसे छोटा पथ खोजने के लिए है। एल्गोरिथ्म का एक एकल निष्पादन शीर्ष के सभी युग्मों के बीच सबसे छोटे पथ की लंबाई का पता लगाएगा।

कोड:

#include
int main() {
int ary[10] = {250,1,9,7,3,4,5,21,15,19};
/यदि हम एक सरणी में n अलग-अलग घटक से 3 घटक लेते हैं तो उनमें से न तो कोई अधिकतम होगा और न ही न्यूनतम।
int a = ary[0];
int b = ary[1];
int c = ary[2];
if((b > a && a >c) || (c > a && a > b)) 
printf("%d",a);
else if((a > b && b >c) || (c > b && b >a)) 
printf("%d",b);
else 
printf("%d",c);
}

आउटपुट: 9

9 न तो अधिकतम है और न ही न्यूनतम है

स्पष्टीकरण:

उपरोक्त कोड में न तो पुनरावृत्ति और न ही पुनरावृत्ति होती है, उपरोक्त प्रोग्राम में प्रत्येक कथन स्थिर समय लेता है

और इसलिए क्रम θ (1) है

नोट: सभी अवयव अलग-अलग हैं, कोई भी तीन संख्याएँ चुनें और उनमें से दूसरा सबसे बड़ा आउटपुट दें। यदि एक ही प्रश्न में 'विशिष्ट' कीवर्ड नहीं दिया गया है, तो हमें 3 अलग-अलग अवयव प्राप्त करने होंगे और सबसे खराब स्थिति में इसमें O(n) समय लगेगा। इन तीन अलग-अलग तत्वों में से मध्य तत्व न तो न्यूनतम है और न ही अधिकतम। इस मामले में यह O(n) है। हमें आशा है कि आपका संदेह दूर हो गया होगा।

बिग - O प्रतीक का एल्गोरिथ्म विश्लेषण:

• बिट - O एल्गोरिथ्म जटिलता ज्ञात करने के लिए प्रयोग किया जाने वाला एक मीट्रिक है।
• यह एल्गोरिथ्म के लिए इनपुट और एल्गोरिथ्म को निष्पादित करने के लिए आवश्यक चरणों के बीच संबंध बताता है।
• इसे प्रारंभिक और समापन कोष्ठक के बाद बिग “O” द्वारा दर्शाया गया है,  इनपुट और एल्गोरिथ्म द्वारा लिए गए चरणों के बीच संबंध n का प्रयोग करके मौजूद होते हैं।
• जालक लूप की समय जटिलता निष्पादित किये जाने वाले आंतरिक कथन की संख्या के बराबर होती है।
• तीन-जालक लूप वाले एल्गोरिथ्म में O(n3) होगा।

सही उत्तर विकल्प 4 है।

अवधारणा :

\(f1 = 2^n, \\ f2 = n^{log n} \\f3 = n^\sqrt{n} , \\ f4 = n^2\)

बड़ा n मान लें,

आइए n=216 पर विचार करें।

फंक्शन की स्पर्शोन्मुख जटिलता का बढ़ता क्रम = f4 , f2 , f3 , f1 है।

अत: सही उत्तर f4 , f2 , f3 , f1 है।

Alternate Method  समय की जटिलताओं के बढ़ते क्रम हैं,

स्थिरांक < लघुगणक < log_squared < रैखिक <  N log N < द्विघात < घन < घातांक

 O(1) < \(1 \over n\)< log n < log2 n < n < nlogn 2 < n3 4 <...<2n <3n < 4n < ....  nn< ... <\({{n}^{n}}^n\)

F1 = 2n = घातांक

F2 = nlogn = घातांक

F3 =\(n^{\sqrt n}\) = घातांक

F4=n2= द्विघात

अत _: F₄ उनमें से सबसे छोटा है।

और शेष F₁ , F₂ , F₃ घातीय फंक्शन हैं इसलिए log₂ को में जोड़ें

F1 = log2 (2n) = n (1) = रैखिक

F2 =log2  (nlogn) = log n log n= log2n = log_squared 

F3 = log2(\(n^{\sqrt n}\)) = \(\sqrt{n} \space log n\) = रैखिक

F4 < F2

F1 = log2 (2n) = n (1) = 216

F3 = log2(\(n^{\sqrt n}\)) = \(\sqrt{n} \space log n\) = \(\sqrt{2^ {16}} \times log 2^{16} \space\) = 28 x 16 =212

F4 < F2 < F3 1

व्याख्या:

f1 = 10n 

log लेने पर

f1 = n× log(10)

f2 = nlogn

log लेने पर

f2 = logn × logn

f3 = n√n

log लेने पर

f3 = √n × logn 

स्पर्शोन्मुख वृद्धि दर: f2 < f3  < f1

इसलिए विकल्प 4 सही है

Important Points

परिणाम को सत्यापित करने के लिए बहुत बड़ी संख्या के बराबर n लें