यह डेटा संरचनाओं और हर व्याख्यान/टीए व्याख्यान में मेरा पहला कोर्स है, हम 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।
http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o/487278#487278 – sank
व्हाउ, 1429 अपवॉट्स की एक संभावित पुनरावृत्ति? मैं अपने विकिपीडिया लिंक के लिए उसमें से आधे से खुश रहूंगा। –