समय जटिलता

Question

यह सवाल एक अतीत परीक्षा कागज मैं सिर्फ यह जानना चाहते हैं मैं सही रास्ते

1. int i=1; 
2. while (i <= n) { 
3. for (int j=1; j<10; j++) 
4.  sum++; 
5. i++; 
6. } 
7. for(int j = 1; j <= n; j++) 
8. for(int k = 1; k <= n; k=k*2) 
9.  sum++; 

1.) कितनी बार बयान 4 निष्पादित किया जाता है पर हूँ चाहता हूँ से संशोधन उद्देश्यों के लिए है?
ए हे (एन)
बी O (n^2)
सी हे (लॉग एन)
डी O (n n लॉग इन करें) ऊपर

यहाँ मैं की
ई कोई भी ए

2.) स्टेटमेंट 9 कितनी बार निष्पादित किया गया है?
ए हे (एन)
बी O (n^2)
सी हे (लॉग एन)
डी O (n n लॉग इन करें) ऊपर

लाइन की वजह से

की
ई कोई भी 8 (के = के * 2) मैंने सी

3.) पूरे कोड खंड का चलने का समय क्या है?
ए हे (एन)
बी O (n^2)
सी हे (लॉग एन)
डी O (n लॉग इन करें n)

के बाद से हे (एन) + O (logn) = ओ (एन) इसलिए मैंने एक

Answer 1

आपका उत्तर 1 सही है, यह केवल n द्वारा नियंत्रित लूप के अंदर है।

उत्तर 2 गलत है। यह O(log n) होगा यदि लाइन 7 मौजूद नहीं था, क्योंकि लाइन 7 n पर निर्भर कई बार चलाने के लिए लाइन 8 और 9 को मजबूर कर रही है, तो उत्तर O(n log n) है।

उत्तर 3 सही तर्क है लेकिन वास्तविक उत्तर 2 से पीड़ित है। O(n) + O(n log n)O(n log n) तक आसान बनाता है।

तो उत्तर A, D और D हैं।

Answer 2

मुझे नहीं पता कि प्रश्न कहां तैयार किए गए हैं, लेकिन यदि शब्द आपके जैसा कहता है, तो आपके परीक्षक को बड़े ओ की सही परिभाषा नहीं पता था (कम से कम जब वह "सही" उत्तरों की अपेक्षा करता है) - "बिग ओ फ़ंक्शन" छोटे शामिल करें "। तो कुछ जो f (n) = 10 n में n के फ़ंक्शन के रूप में निष्पादित करता है जो रैखिक है ओ (एन), ओ (एन^2), ओ (एन लॉग एन) में भी है। एक "छोटी से छोटी" संभव लिए पूछता है, अपने जवाब

1. इसलिए वक्तव्य 4 निष्पादित किया जाता है 10 n बार है, तो एक
2. वक्तव्य 9 निष्पादित किया जाता है n * लोग इन n बार, डी
3. यहाँ होगा इसे दोनों के योग को निष्पादित किया जाता है, एन + एन * लॉग एन इसलिए (यहां आप एक * एन खो गए हैं), इसलिए डी सही होगा।

तो अगर एकाधिक जवाब संभव थे और यह सिर्फ यह कितना क्रियान्वित किया जाता है के लिए कहा गया था, सही जवाब होगा

1. ए, बी, डी
2. बी, डी
3. बी , डी

Answer 3

उत्तर 1: यानी। ओ (एन) कथन 4 के रूप में 10 * एन बार निष्पादित किया जाएगा।

उत्तर 2: डी यानी। ओ (एनएलओएल (एन)) कथन 9 के रूप में एन * लॉग (एन) बार निष्पादित किया जाएगा।

उत्तर 3: डी समग्र जटिलता के रूप में [ओ (एन) + ओ (एनएलओएल (एन))] एन * लॉग (एन) होगा।