बड़ा-ओ नोटेशन क्या है? आप ओ (एन) जैसे आंकड़ों के साथ कैसे आते हैं?

Question

संभव डुप्लिकेट:
Plain english explanation of Big O

मैं कल्पना करता है कि यह शायद कुछ कक्षाओं में पढ़ाया जाता है, लेकिन मैं एक आत्म सिखाया प्रोग्रामर के रूप में, मैं सिर्फ यह शायद ही कभी देखा है।

मैंने इकट्ठा किया है कि यह समय के साथ कुछ करने के लिए है, और ओ (1) सबसे अच्छा है, जबकि ओ (एन^एन) जैसी चीजें बहुत खराब हैं, लेकिन क्या कोई मुझे मूलभूत व्याख्या के बारे में बता सकता है यह वास्तव में प्रतिनिधित्व करता है, और ये संख्या कहां से आती है?

Answer 1

बिग ओ सबसे खराब केस रन-टाइम ऑर्डर को संदर्भित करता है। यह डेटा सेट (एन-> वस्तुओं की संख्या) के आकार के आधार पर एल्गोरिदम स्केल कितनी अच्छी तरह से दिखाने के लिए प्रयोग किया जाता है।

चूंकि हम केवल आदेश से चिंतित हैं, निरंतर गुणक अनदेखा कर रहे हैं, और किसी भी शब्द जो प्रभावी अवधि से कम तेज़ी से बढ़ते हैं, भी हटा दिए जाते हैं। कुछ उदाहरण:

एक एकल ऑपरेशन या संचालन का सेट ओ (1) है, क्योंकि इसमें कुछ स्थिर समय लगता है (डेटा सेट आकार के आधार पर भिन्न नहीं होता है)।

एक लूप ओ (एन) है। डेटा सेट में प्रत्येक तत्व looped है।

एक नेस्टेड लूप ओ (एन^2) है। एक नेस्टेड नेस्टेड लूप ओ (एन^3), और आगे है।

बाइनरी पेड़ खोज जैसी चीजें लॉग (एन) हैं, जो दिखाना अधिक कठिन है, लेकिन पेड़ में हर स्तर पर, समाधान की संभावित संख्या कम हो जाती है, इसलिए स्तरों की संख्या लॉग (एन) (प्रदान की जाती है) पेड़ संतुलित है)।

किसी दिए गए मान के निकटतम संख्याओं के सेट को खोजने की तरह कुछ है ओ (एन!), क्योंकि प्रत्येक सबसेट की गणना की गणना की आवश्यकता है। यह बहुत बुरा है।

Answer 2

यह समय जटिलता व्यक्त करने का एक तरीका है।

O(n) किसी सूची में n तत्वों के लिए है, तो सूची को क्रमबद्ध करने के लिए n गणनाएं होती हैं। जो बिल्कुल बुरा नहीं है। n में प्रत्येक वृद्धि समय जटिलता को रैखिक रूप से बढ़ाती है।

O(n^n) खराब है, क्योंकि एक प्रकार (या जो भी आप कर रहे हैं) करने के लिए आवश्यक गणना की मात्रा तेजी से बढ़ जाएगी क्योंकि आप n बढ़ाते हैं।

O(1) सबसे अच्छा है, क्योंकि इसका मतलब है कि फ़ंक्शन करने के लिए 1 गणना, हैश टेबल के बारे में सोचें, हैश तालिका में एक मान को देखकर O(1) समय जटिलता है।

Answer 3

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

बड़े ओ नोटेशन में, ब्रैकेट्स में अभिव्यक्ति वह कार्य है जो पकड़ा जाता है।यदि अभिव्यक्ति में एक चर (कहें एन) शामिल है, तो यह चर इनपुट डेटा सेट के आकार को संदर्भित करता है। आप कहते हैं ओ (1) सबसे अच्छा है। यह सच है क्योंकि ग्राफ f (n) = 1 n के साथ भिन्न नहीं है। एक ओ (1) एल्गोरिदम इनपुट डेटा सेट के आकार के बावजूद पूरा करने के लिए एक ही समय लेता है। इसके विपरीत, ओ (एन^एन) के एल्गोरिदम का रन टाइम इनपुट डेटा सेट के आकार के वर्ग के साथ बढ़ता है।

विस्तृत विवरण के लिए यह मूल विचार है, 'बिग ओ नोटेशन' नामक विकिपीडिया पेज से परामर्श लें।