समय जटिलता गणना

Question

मैं वर्तमान में कुछ परीक्षा प्रश्न काम कर रहा हूं, और इस बिंदु पर अटक गया। मुझे दिया गया है कि एक क्विक्सोर्ट एल्गोरिदम में O(nlog(n)) की समय जटिलता है। किसी विशेष इनपुट आकार के लिए, सूची को सॉर्ट करने का समय 4 मिनट है। सवाल यह पूछने के लिए आता है कि उसी प्रणाली पर आकार के दो बार सूची को क्रमबद्ध करने में कितना समय लगेगा।

मैंने पहले से ही इनकार कर दिया है कि समय 8 मिनट नहीं है (दो बार इनपुट आकार = दो बार अवधि, बहुत गलत तर्क)।

कुछ काम कर मैंने किया:

कार्य एक

• 4 = nlog(n)
• 4 = log(n^n)
• 16 = n^n
• मैं मूल रूप से इस बिंदु पर अटक गई।

कार्य बी

• X = 2nlog(2n) >> 2n डबल इनपुट के बाद से
• X = 2n(1 + log(n))
• X = 2n + 2nlog(n) >> nlog(n)4 मिनट
• X = 2n + 2(4) = 2n + 8
• मैं एक बार फिर इस बिंदु पर अटक गया था।

Answer 1

मुझे लगता है कि इस समस्या के बारे में ध्यान देने वाली पहली बात यह है कि, संख्याओं को क्रमबद्ध करने में 4 मिनट लग गए, n काफी बड़ा होना चाहिए। उदाहरण के लिए, मैंने अपने कंप्यूटर पर एक बिलियन नंबरों को सॉर्ट करने के लिए क्विकॉर्ट का उपयोग किया, और इसमें केवल 3 मिनट लग गए। तो n शायद लगभग 1 बिलियन है (परिमाण का आदेश दें या लें)।

यह देखते हुए कि n बहुत बड़ा है, यह कुछ निरंतर c के लिए c*n*lg(n) के रूप में इस क्रम अनुमान लगाने के लिए, के बाद से क्रम विस्तार के निचले क्रम के मामले इतनी बड़ी n के लिए भी प्रासंगिक नहीं होने चाहिए संभावना उचित है। हम दोगुना n, तो हम मूल क्रम की तुलना में क्रम के निम्नलिखित गुणक मिलती है:

[Runtime(2n)]/[Runtime(n)] 
[c * (2n) * lg(2n)]/[c * n * lg(n)] 
2 * lg(2n)/lg(n) 
2 * log_n(2n) 
2 * (1 + log_n(2)) 

यहाँ, lg() एक मनमाना आधार के नीचे लघुगणक है और log_n() लॉग आधार n है।

सबसे पहले, क्योंकि हम मान लिया n बड़ी है, आगे बढ़ने के लिए एक संभव तरीके से 0 के रूप में log_n(2) अनुमान लगाने के लिए है, इसलिए क्रम गुणक 2 के रूप में अनुमानित किया जाएगा और कुल रनटाइम 8 मिनट के रूप में अनुमान लगाया जा होगा।

• तो n = 100 मिलियन है, तो हम अनुमान लगा होगा:

  वैकल्पिक रूप से, क्योंकि हम शायद परिमाण के एक आदेश के भीतर करने के लिए n पता है, एक और संभावना n की संभावना मूल्य के लिए गुणक अनुमान लगाने के लिए किया जाएगा 2.075 के रूप में गुणक और कुल रनटाइम 8.30 मिनट के रूप में।

• यदि n = 1 बिलियन, तो हम गुणक को 2.067 के रूप में अनुमानित करेंगे और कुल रनटाइम 8.27 मिनट के रूप में अनुमानित करेंगे।
• यदि n = 10 बिलियन, तो हम गुणक को 2.060 के रूप में अनुमानित करेंगे और कुल रनटाइम 8.24 मिनट के रूप में अनुमानित करेंगे।

यहां ध्यान दें कि n के हमारे अनुमान में भारी परिवर्तन कुल रनटाइम के अनुमान में बहुत छोटे बदलाव उत्पन्न करते हैं।

यह ध्यान देने योग्य है कि, यह कागज पर अच्छा लग रहा है, प्रैक्टिस में आर्किटेक्चरल विचारों से वास्तविक जीवन रनटाइम उन लोगों से बहुत अलग हो सकते हैं जिनकी हमने गणना की है। उदाहरण के लिए, यदि एल्गोरिदम डेटा आकार को दोगुना करने के बाद पेजिंग का एक गुच्छा लाता है, तो रनटाइम बहुत अधिक हो सकता है, जो हमने अनुमानित ~ 8 मिनट से कहीं अधिक है।

Answer 2

एन के मूल्य को जानने के बिना पूर्ण समय की गणना करना संभव नहीं है।
कुछ अनुभवजन्य मूल्यों के माध्यम से इसे लें।
मान लें 'k' समय एक ही आपरेशन

If, n = 2, k.n.log(n) = 4 => k.2.1 = 4 => k = 2 
    if n is doubled, k.2n.log(2n) = 2.4.2 => 16 minutes 

If, n = 4, k.n.log(n) = 4 => k.4.2 = 4 => k = 1/2 
    if n is doubled, k.2n.log(2n) = 1/2.8.3 => 12 minutes 

If, n = 64, k.n.log(n) = 4 => k.64.6 = 4 => k = 1/96 
    if n is doubled, k.2n.log(2n) = 1/96.128.7 => 9.33 minutes 

n बढ़ने के साथ

तो के लिए लिया है, समय लिया (8 मिनट) दो बार समय के करीब आता है

Answer 3

उपलब्ध कराई गई जानकारी है अपूर्ण।

सबूत:

एल्गोरिथम जटिलता O(nlogn) बनें। इसका मतलब है कि समय लिया गया, t = c*nlogn।

इसलिए, हम निम्नलिखित समीकरण है:

• 4 = c*n*logn
• t = c*(n2)*log(n2), जहां t आवश्यक जवाब
• n2 = 2*n2

चर = 4 (n, n2 की संख्या है, t, c)
अद्वितीय समीकरणों की संख्या = 3
चूंकि हमें 4 चर के लिए कम से कम 4 समीकरणों की आवश्यकता है, इसलिए प्रदान की गई जानकारी अपूर्ण है।

Answer 4

मुझे @ अमितोज के तर्क पसंद हैं, लेकिन मैं इसे सामान्यीकृत करता हूं।

n0 = 4 मिनट के रन टाइम में परिणाम वाले तत्वों की संख्या, और n1 = 2 * n0। फिर हम

c = 4 mins/(n0 * log n0) 

है हम खोजने के लिए

t = c * n1 * log n1 
    = 4 mins/(n0 * log n0) * n1 * log n1 
    = 4 mins * (n1/n0) * (log n1/log n0) 

n1/n0 हमेशा = 2.

N0 => अनंत के रूप में है कोशिश कर रहे हैं, log n1/log n0 की सीमा 1.

को जाता है तो हाँ, जैसे n0 बड़ा हो जाता है, टी की सीमा 4 mins * 2 = 8 mins है।

Answer 5

Anmol Singh Jaggi को छोड़कर सभी उत्तरों गलत हैं।

सबसे पहले यह देखना आसान है कि यह जानकारी उत्तर देने के लिए पर्याप्त नहीं है। और यही कारण है कि:

आपको समीकरण को हल करने के लिए केवल इतना करना है। अपने एल्गोरिथ्म के समय जटिलता O (n logn) है, तो पहले समीकरण आपके पास है:

जहां अपनी सूची के आकार में n। आप 2 समीकरणों की एक प्रणाली को हल करने की जरूरत है

तो मूल रूप से: यदि वे आप कितना समय यह तुम्हें लेने दो बार बड़ा के रूप में आकार के लिए एल्गोरिथ्म समाप्त करने के लिए होगा खोजना चाहते हैं, वे मूल रूप से x लगाना चाहते हैं 3 अज्ञात के साथ। इसमें या तो 0 उत्तर हैं (हमारे मामले में नहीं) या अनंत उत्तरों की संख्या।

---

अब आपको अपने सी 1 की धारणा बनाना है। यदि c1 = 1, तो

दूसरे समीकरण आप प्राप्त करने के लिए n स्थानापन्न: x = 13.5। तो 13 और आधे मिनट।

---

लेकिन एक बार और, इस सवाल का जवाब हम इस धारणा पर है कि c1 1 के बराबर है, यदि आप एक और निरंतर कारक है, तो आप एक और जवाब मिल जाएगा।

Answer 6

यह एक बिल्कुल भयानक परीक्षा प्रश्न की तरह लगता है, शायद किसी ऐसे व्यक्ति द्वारा लिखित जिसे बिग-ओ नोटेशन वास्तव में क्या है, इसकी गहरी समझ नहीं है। इसमें बहुत गड़बड़ है - जिनमें से अधिकतर पहले से ही अन्य उत्तरों में संबोधित किया गया है।

सबसे बड़ी समस्या यह है कि बिग-ओ नोटेशन आपको वास्तविक समय से कोई सीधा संबंध नहीं देता है। यह एक बड़ी मात्रा में जानकारी फेंकता है जिसे पूछे जाने वाले वास्तविक प्रश्न का उत्तर देने की आवश्यकता होगी।

अन्य उत्तरों ने यहां बताया है कि प्रश्न आपको इनपुट के मूल सेट में कितने आइटम थे, केवल यह संकेत नहीं देता कि केवल दूसरे सेट में दो बार हैं, और यह जानकारी महत्वपूर्ण है जवाब देने के लिए। लेकिन कुछ चीजें हैं जिनके बारे में उन्होंने उल्लेख नहीं किया ...

सबसे पहले, बिग-ओ एल्गोरिदम ओवरहेड्स को अनदेखा करता है। यह मामला हो सकता है कि एल्गोरिदम का उपयोग वास्तव में 3.5 मिनट लगते हैं, इस पर ध्यान दिए बिना कि कितने इनपुट प्राप्त होते हैं, और इनपुट के मूल सेट के लिए वास्तविक प्रसंस्करण समय केवल 30 सेकंड था। यह इनपुट की किसी भी मनमानी संख्या के लिए किए गए समय की गणना को गंभीरता से प्रभावित करेगा।

लेकिन जितना बुरा हो उतना बुरा है, बिग-ओ इसे और भी आगे ले जाता है। Wikipedia से इस उद्धरण के बाहर

की जांच:

विशिष्ट उपयोग में, हे संकेतन की औपचारिक परिभाषा सीधे इस्तेमाल नहीं किया है; बल्कि, एक समारोह च के लिए हे संकेतन निम्नलिखित सरलीकरण नियमों से लिया गया है:

• f (x) कई शब्दों में से एक योग है, तो सबसे बड़ा विकास दर के साथ एक रखा जाता है, और अन्य सभी को छोड़ दिया।
• यदि एफ (एक्स) कई कारकों का उत्पाद है, तो किसी भी स्थिरांक (उत्पाद में शर्तें जो x पर निर्भर नहीं हैं) छोड़ी जाती हैं।

इसका मतलब क्या है कि समय गणना अनेक शब्दों है कि अंततः छोड़ दिए जाते हैं शामिल कर सकते हैं। क्या होगा यदि एल्गोरिदम c * (n + n * log(n)) पूरा करने के लिए समय लेता है, बिना ओवरहेड के? बिग-ओ नोटेशन में यह अभी भी O(nlogn) है।

परीक्षा प्रश्न के लिए वास्तव में संभव है कि एकमात्र उत्तर "कुछ मिनट से अधिक समय" है। हम बहुत अधिक जानकारी के बिना उससे कुछ और नहीं जान सकते हैं। विशेष रूप से:

• ओवरहेड क्या है?
• प्रति ऑपरेशन समय की लागत क्या है?
• हम कितने आइटम के बारे में बात कर रहे हैं?
• अन्य शर्तें क्या हैं?