यह डेटा संरचनाओं और हर व्याख्यान/टीए व्याख्यान में मेरा पहला कोर्स है, हम O(log(n))
के बारे में बात करते हैं। यह शायद एक बेवकूफ सवाल है, लेकिन अगर कोई मुझे समझा सकता है तो मैं सराहना करता हूं कि इसका क्या अर्थ है!ओ (एन) और ओ (लॉग (एन)) के बीच अंतर - जो बेहतर है और ओ (लॉग (एन)) वास्तव में क्या है?
उत्तर
इसका मतलब है कि प्रश्न (आमतौर पर चलने का समय) इस तरह के पैमाने पर स्केल करता है जो उसके इनपुट आकार के लॉगेरिथम के अनुरूप होता है।
Big-O notation एक सटीक समीकरण मतलब यह नहीं है, बल्कि एक बाध्य। उदाहरण के लिए, निम्नलिखित कार्य के उत्पादन में सभी हे (एन) है:
f(x) = 3x
g(x) = 0.5x
m(x) = x + 5
क्योंकि जैसा कि आप एक्स, उनके outputs सभी वृद्धि रैखिक वृद्धि - हो, तो एक 6: f(n)
और g(n)
के बीच 1 अनुपात, वहाँ भी होगा f(10*n)
और g(10*n)
और इसी तरह के बीच लगभग 6: 1 अनुपात बनें।
के लिए कि क्या O(n)
या O(log n)
बेहतर है के रूप में, पर विचार करें: यदि n = 1000
, तो log n = 3
(लॉग-आधार -10 के लिए)। आप अपने एल्गोरिदम को चलाने के लिए क्या लेते हैं: 1000 सेकंड, या 3 सेकंड?
अच्छी तरह से समझाया। साथ ही, मैं कुछ जानकारी जोड़ना चाहता हूं कि लॉगरिथम उन लोगों के लिए भी है जो नहीं जानते हैं। कंप्यूटर विज्ञान में लॉग एन का मतलब है, एक्सपोनेंट मुझे एन प्राप्त करने के लिए नंबर 2 बढ़ाने की आवश्यकता होगी। तो कल्पना करें, अगर एन = 16. हमारा एक्सपोनेंट वास्तविक एन मान से बहुत छोटा होगा। यह 4 होगा। उम्मीद है कि यह समझ में आता है। एम्बर द्वारा उपरोक्त उदाहरण में, वह एक समान उदाहरण दे रही है लेकिन 3. –
+1 की शक्ति में 10 को बढ़ा रही है - शब्दों की सबसे छोटी संख्या में स्पष्ट स्पष्टीकरण संभव है। धन्यवाद। – techfoobar
http://en.wikipedia.org/wiki/Big_oh
हे (लॉग एन) बेहतर है।
ओ (लॉगन) का अर्थ है कि एल्गोरिदम का चलने का समय इनपुट आकार के लॉगरिदम पर निर्भर है। ओ (एन) का अर्थ है कि एल्गोरिदम का चलने का समय इनपुट आकार पर निर्भर है।
मूल रूप से, ओ (कुछ) एल्गोरिदम की निर्देशों (परमाणु वाले) पर ऊपरी बाध्य है। इसलिए, ओ (लॉगन) ओ (एन) से कड़ा है और एल्गोरिदम विश्लेषण के मामले में भी बेहतर है। लेकिन सभी एल्गोरिदम हैं कि हे (logn) भी हे (एन) हैं, लेकिन नहीं पीछे की ओर ...
"ओ (एन) ओ (लॉग) से अधिक कठिन है और एल्गोरिदम विश्लेषण के संदर्भ में भी बेहतर है" ... स्पष्ट रूप से ओ (लॉग (एन)) ओ (एन) से बेहतर है। मुझे लगता है कि आप दूसरे तरीके से मतलब है। – LuxuryMode
मूर्खतापूर्ण :) संपादित – Eyal
आकार n
के इनपुट के लिए, O(n)
की एक एल्गोरिथ्म कदम, n
को perportional प्रदर्शन करेंगे जबकि O(log(n))
का एक और एल्गोरिथ्म लगभग log(n)
कदम उठाएंगे।
स्पष्ट रूप से log(n)
n
से छोटा है इसलिए जटिलता O(log(n))
की एल्गोरिदम बेहतर है। चूंकि यह बहुत तेज होगा।
औपचारिक परिभाषा:
जी (x) = ओ (f (x)) < => x0 और निरंतर सी है कि वहाँ हर x> x0 के लिए, | g (x) | < = सी | एफ (एक्स) |
इस प्रकार, आप समस्या पी के लिए एल्गोरिथ्म एक इसकी जटिलता हे (च (एन)), आप कह सकते हैं कि कि कदम अपने एल्गोरिथ्म क्या करेंगे की संख्या, कम या asymptotically च (एन) के बराबर है पाते हैं, जब एन आमतौर पर इनपुट आकार होता है। (एन कुछ भी हो सकता है)
आगे पढ़ने के लिए: http: //en.wikipedia.org/wiki/Big_O_notation।
- 1. आप ओ (लॉग एन) और ओ (एन लॉग एन) के बीच अंतर कैसे देखते हैं?
- 2. ओ (लॉग) हमेशा ओ (एन)
- 3. ओ (एन लॉग एन) समय
- 4. बिग ओह नोटेशन ओ ((लॉग एन)^के) = ओ (लॉग एन)?
- 5. ओ (लॉग एन)
- 6. ओ (लॉग एन)
- 7. ओ (एन)
- 8. ओ क्या करता है (लॉग (लॉग (एन))) - प्रतिस्पर्धी मतलब?
- 9. ओ (एन) समय
- 10. ओ (एन) समय
- 11. एक ओ (एन) सॉर्टिंग एल्गोरिदम
- 12. थोड़ा स्थानांतरण ओ (1) या ओ (एन) है?
- 13. ओ (एन लॉग एन) से जेनेरिक और व्यावहारिक सॉर्टिंग एल्गोरिदम तेजी से?
- 14. एक स्ट्रिंग ओ (एन लॉग एन) को सॉर्ट क्यों कर रहा है?
- 15. बबल सॉर्ट ओ (एन^2) क्यों है?
- 16. ओ (एन) संख्याओं के संग्रह के औसत को खोजने के लिए ओ (एन) एल्गोरिदम
- 17. क्या ओ (एन लॉग एन) से बेहतर संख्याओं की सूची के औसत की गणना करना संभव है?
- 18. इसका क्या अर्थ है: ओ (एन) चरण और ओ (1) अंतरिक्ष?
- 19. क्या कोई ओ (एन) पूर्णांक सॉर्टिंग एल्गोरिदम है?
- 20. ओ (2^एन) से बेहतर हनोई समाधान के टावर्स?
- 21. सी # सूची अंत से हटा दें, वास्तव में ओ (एन)?
- 22. जावा टाइम कॉम्प्लेक्सिटी ओ (एन^2/3)
- 23. बड़ा-ओ नोटेशन क्या है? आप ओ (एन) जैसे आंकड़ों के साथ कैसे आते हैं?
- 24. क्या अधिकतम हेप बनाने के लिए ओ (एन) एल्गोरिदम है?
- 25. ओ (एन) से बेहतर एक रेंज चौराहे एल्गोरिदम?
- 26. ओ (एन * लॉग (एन)) में दिए गए योग और उत्पाद के साथ सरणी तत्वों की एक जोड़ी खोजें
- 27. ग्राफ में नया किनारा जोड़ें और ओ (एन)
- 28. क्या एपेंड प्रक्रिया ओ (एन) का रनटाइम है?
- 29. "$^एन" और "$ +" के बीच क्या अंतर है?
- 30. आई/ओ बंदरगाहों और आई/ओ मेमोरी के बीच अंतर
http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o/487278#487278 – sank
व्हाउ, 1429 अपवॉट्स की एक संभावित पुनरावृत्ति? मैं अपने विकिपीडिया लिंक के लिए उसमें से आधे से खुश रहूंगा। –