बड़े ओ नोटेशन

Question

के साथ सहायता मुझे बड़ी ओ नोटेशन की अवधारणा को समझने की कोशिश करने में कुछ समस्याएं आ रही हैं। तो, परिभाषा के अनुसार बड़े ओ इस प्रकार है, T(n) ∈ O(G(n)) if T(n) <= G(n) * C।

चूंकि निरंतर "सी" कोई पूर्णांक हो सकता है> 0, क्या यह निम्न उदाहरण भी सत्य नहीं होगा?

उदाहरण:

n log n ∈ O(log n) 
n log n <= log n * c 

कहाँ सी n के मूल्य के बराबर है।

मुझे पता है कि उत्तर n log n ∉ O(log n) है लेकिन मुझे समझ में नहीं आता कि सी कैसे स्थिर हो सकता है।

आपकी मदद के लिए अग्रिम धन्यवाद: डी

Answer 1

ग सिर्फ इतना है कि, एक निरंतर है। इसका मतलब यह है कि आप "सी को मान का मूल्य होने दें" नहीं कह सकते हैं, क्योंकि आपको पहले कुछ सी चुनना होगा और फिर सभी एन के लिए तुलना करने की अनुमति दें।

दूसरे शब्दों में, कुछ टी (एन) ओ (जी (एन)) के लिए, नहीं निरंतर सी मौजूद होना चाहिए जैसे जी (एन) * सी टी (एन) से अधिक है सब एन

इस प्रकार n लॉग n ओ (लॉग एन) नहीं है, इससे कोई फर्क नहीं पड़ता कि आप जो भी स्थिर चुनते हैं, n> c n लॉग n n c लॉग n से अधिक होने का कारण बनता है।

Answer 2

मुझे अपने शब्दों को दोहराने दो।

सी स्थिर हो सकता है।

इसका मतलब है कि सी एन पर निर्भर नहीं हो सकता है।

Answer 3

विचार यह है कि असमानता किसी भी एन और निश्चित सी के लिए होती है। इसलिए जब आपको एक निश्चित सी मिल सकता है जैसे कि n लॉग n < c लॉग n, (अर्थात् कोई सी> एन), आप आसानी से अन्य n 'ढूंढ सकते हैं जिसके लिए यह नहीं है (अर्थात् n'> c)।

Answer 4

परिभाषा में आपको केवल टी और जी द्वारा सी निर्धारित करना चाहिए। यह एक निरंतर सी मतलब है। इसलिए सी को उनके इनपुट पर निर्भर नहीं होना चाहिए। तो आप अभिव्यक्ति एन लॉग एन में सी = एन

Answer 5

पर विचार नहीं कर सकते हैं, आप बाहरी एन से सी की तुलना नहीं कर सकते, जैसा कि आप कर रहे हैं। यह अल्ग्रेब्रिक एक्सप्रेशन एक्स (एक्स + 1) लेने और एक्स के एक स्थिर को स्थिर रखने की तरह होगा।

एन लॉग एन में, एन एक चर है। बड़े ओ एक्सप्रेशन में, सी स्थिर है।

Answer 6

एन का मान इनपुट सेट पर निर्भर करता है, सी का मान तय किया जाता है।

तो हाँ, अगर एन = 16 और सी = 256, यह एक छोटे इनपुट सेट के लिए n^2 * lg (n) जैसा दिखता है। अब इनपुट सेट को 100,000,000 तक बढ़ाएं; सी का मूल्य 256 पर रहता है, अब आपके पास 256 * एलजी (100,000,000)

Answer 7

सबसे पहले, यदि एन = सी तो सी स्थिर नहीं है। और अधिकांश वास्तविक दुनिया एल्गोरिदम में, सी छोटा है इसलिए बड़े-ओ भाग आमतौर पर एन के विशिष्ट मानों के लिए हावी होते हैं।

लेकिन बड़े-ओ जटिलता बड़े एन के लिए एल्गोरिदम की दक्षता से संबंधित है, विशेष रूप से एन अनन्तता के दृष्टिकोण के रूप में। दूसरे शब्दों में यह आपको एल्गोरिदम की स्केलेबिलिटी बताता है: कितना अच्छा दिया गया एल्गोरिदम एक बहुत बड़ा या दोगुना वर्कलोड संभालता है।

यदि आप जानते हैं कि n हमेशा छोटा है तो बड़ी-जटिलता महत्वपूर्ण नहीं है, बल्कि आपको एल्गोरिदम द्वारा आवश्यक दीवार घड़ी के समय पर ध्यान देना चाहिए। इसके अलावा, यदि आप दो एल्गोरिदम के बीच चयन कर रहे हैं जिनमें एक ही बड़ी-ओ जटिलता है (उदा। ओ (एन लॉग एन)), अक्सर एक दूसरे की तुलना में बेहतर होता है (उदाहरण के लिए यादृच्छिक-पिवोट क्विकॉर्ट आमतौर पर बाइनरी हीप सॉर्ट से बेहतर प्रदर्शन करता है)।

Answer 8

जब भी मैं बड़े-बड़े पर फंस जाता हूं, मुझे इसे प्रतिस्पर्धा के रूप में सोचने में उपयोगी लगता है: मैं एक बड़ा ओह फ़ंक्शन चुनता हूं (इसलिए, आपके मामले में, लॉगऑन) और निरंतर (सी)। महत्वपूर्ण बात यह है कि मुझे एक वास्तविक मूल्य चुनना है। मैं आमतौर पर एक हज़ार चुनता हूं, सिर्फ इसलिए। फिर मुझे अपने arch-nemesis को चुनने देना है, वह चुनता है। वह आम तौर पर एक अरब चुनता है।

फिर मैं तुलना करता हूं।

उदाहरण को समाप्त करने के लिए, 10^9 * (लॉग (10^9)) अब 1000log (10^9) से काफी बड़ा बना दिया गया है। इस प्रकार, मुझे पता है कि बड़ा ओह काम नहीं करेगा।

Answer 9

मुझे लगता है कि यह लिंक आपके लिए चीजों को स्पष्ट कर सकता है।

http://mohalgorithmsorbit.blogspot.com/2013/12/complexity-theory-approaching.html