algorithm - "बिग ओ" नोटेशन का सादा अंग्रेजी स्पष्टीकरण क्या है?




complexity-theory computer-science big-o time-complexity (25)

मैं जितनी कम औपचारिक परिभाषा को संभव और सरल गणित के रूप में पसंद करूंगा।


Answers

यह एक बहुत ही सरल व्याख्या है, लेकिन मुझे आशा है कि इसमें सबसे महत्वपूर्ण विवरण शामिल होंगे।

आइए मान लें कि समस्या से निपटने वाला आपका एल्गोरिदम कुछ 'कारकों' पर निर्भर करता है, उदाहरण के लिए चलिए इसे एन और एक्स बनाते हैं।

एन और एक्स के आधार पर, आपके एल्गोरिदम को कुछ परिचालनों की आवश्यकता होगी, उदाहरण के लिए सबसे अच्छे मामले में यह 3(N^2) + log(X)संचालन है।

चूंकि बिग-ओ निरंतर कारक (उर्फ 3) के बारे में बहुत अधिक परवाह नहीं करता है, इसलिए आपके एल्गोरिदम का बिग-ओ है O(N^2 + log(X))। यह मूल रूप से 'आपके एल्गोरिदम को इस तरह के सबसे खराब केस स्केल के लिए आवश्यक संचालन की मात्रा' का अनुवाद करता है।


यदि आपके सिर में अनंतता की उपयुक्त धारणा है, तो एक बहुत संक्षिप्त विवरण है:

बिग ओ नोटेशन आपको असीम बड़ी समस्या को हल करने की लागत बताता है।

और इसके अलावा

लगातार कारक नगण्य हैं

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

हालांकि, निरंतर कारक से कुछ भी "बड़ा" पाया जा सकता है, हालांकि।

जब कम्प्यूटेशंस करने में दिलचस्पी होती है जिसका आकार "बड़ा" होता है जिसे लगभग अनंतता माना जाता है, तो बड़ी ओ नोटेशन आपकी समस्या को हल करने की लागत लगभग है।

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


बिग ओ एक एल्गोरिदम की मौलिक स्केलिंग प्रकृति का वर्णन करता है।

बहुत सारी जानकारी है कि बिग ओ आपको दिए गए एल्गोरिदम के बारे में नहीं बताता है। यह हड्डी में कटौती करता है और एक एल्गोरिदम की स्केलिंग प्रकृति के बारे में केवल जानकारी देता है, विशेष रूप से "इनपुट आकार" के जवाब में एल्गोरिदम स्केल के संसाधन का उपयोग (सोचने का समय या स्मृति)।

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

यह क्यों इतना महत्वपूर्ण है? चूंकि सॉफ़्टवेयर उन समस्याओं से संबंधित है जो ट्रिलियन तक कारकों के आकार में भिन्न हो सकते हैं। एक पल के लिए विचार करें। चंद्रमा और मानव चलने की गति के लिए आवश्यक गति के बीच अनुपात 10,000: 1 से कम है, और इनपुट आकार सॉफ़्टवेयर में सीमा की तुलना में यह बिल्कुल छोटा है। और क्योंकि सॉफ़्टवेयर इनपुट आकारों में खगोलीय सीमा का सामना कर सकता है, इसलिए एल्गोरिदम की बिग ओ जटिलता की संभावना है, यह किसी भी कार्यान्वयन विवरण को टंप करने के लिए मौलिक स्केलिंग प्रकृति है।

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


प्रस्तावना

एल्गोरिदम : किसी समस्या को हल करने के लिए प्रक्रिया / सूत्र

एल्गोरिदम का विश्लेषण कैसे करें और हम एक दूसरे के खिलाफ एल्गोरिदम की तुलना कैसे कर सकते हैं?

उदाहरण: आप और एक दोस्त को 0 से एन तक संख्याओं को योग करने के लिए एक फ़ंक्शन बनाने के लिए कहा जाता है। आप f (x) के साथ आते हैं और आपका मित्र जी (x) के साथ आता है। दोनों कार्यों का एक ही परिणाम है, लेकिन एक अलग एल्गोरिदम है। एल्गोरिदम की दक्षता की तुलनात्मक रूप से तुलना करने के लिए हम बिग-ओ नोटेशन का उपयोग करते हैं ।

बिग-ओ नोटेशन: यह बताता है कि इनपुट के सापेक्ष कितनी जल्दी रनटाइम बढ़ेगा क्योंकि इनपुट मनमाने ढंग से बड़ा हो जाता है।

3 कुंजी टेकवेज़:

  1. तुलना करें कि रनटाइम कितनी जल्दी बढ़ता है सटीक रनटाइम की तुलना नहीं करता है (हार्डवेयर पर निर्भर करता है)
  2. इनपुट के सापेक्ष केवल रनटाइम के साथ चिंतित (एन)
  3. चूंकि n मनमाने ढंग से बड़ा हो जाता है, उन शर्तों पर ध्यान केंद्रित करें जो तेजी से बढ़ेगा क्योंकि एन बड़ा हो जाता है (अनंतता सोचें) AKA एसिम्प्टोटिक विश्लेषण

अंतरिक्ष जटिलता: समय जटिलता के अलावा, हम अंतरिक्ष जटिलता (कितनी स्मृति / स्थान एल्गोरिदम का उपयोग करता है) के बारे में भी परवाह करते हैं। संचालन के समय की जांच करने के बजाय, हम स्मृति के आवंटन के आकार की जांच करते हैं।


बिग ओ

एफ (एक्स) = ओ ( जी (एक्स)) जब एक्स एक (उदाहरण के लिए, एक = + ∞) का मतलब है कि एक फ़ंक्शन k ऐसा है कि:

  1. एफ (एक्स) = के (एक्स) जी (एक्स)

  2. के कुछ पड़ोस में बाध्य है (यदि एक = + ∞, इसका मतलब है कि संख्याएं एन और एम हैं जैसे कि प्रत्येक एक्स> एन, | के (एक्स) | <एम) के लिए।

दूसरे शब्दों में, सादे अंग्रेजी में: f (x) = O ( g (x)), x → a, का अर्थ है कि एक के पड़ोस में, f g और कुछ बाध्य फ़ंक्शन के उत्पाद में विघटित होता है।

छोटा ओ

वैसे, यहां छोटे ओ की परिभाषा की तुलना करने के लिए है।

एफ (एक्स) = ओ ( जी (एक्स)) जब एक्स एक माध्यम से जाता है कि एक समारोह k ऐसा होता है कि:

  1. एफ (एक्स) = के (एक्स) जी (एक्स)

  2. के (एक्स) 0 पर जाता है जब एक्स एक जाता है।

उदाहरण

  • पाप एक्स = ओ (एक्स) जब एक्स → 0।

  • पाप x = ओ (1) जब x → + ∞,

  • एक्स 2 + एक्स = ओ (एक्स) जब एक्स → 0,

  • एक्स 2 + एक्स = ओ (एक्स 2 ) जब एक्स → + ∞,

  • एलएन (एक्स) = ओ (एक्स) = ओ (एक्स) जब एक्स → + ∞।

ध्यान! बराबर चिह्न "=" के साथ नोटेशन "नकली समानता" का उपयोग करता है: यह सच है कि ओ (जी (एक्स)) = ओ (जी (एक्स)), लेकिन गलत है कि ओ (जी (एक्स)) = ओ (जी (एक्स))। इसी प्रकार, "ln (x) = o (x) लिखना ठीक है जब x → + ∞", लेकिन सूत्र "ओ (x) = ln (x)" कोई अर्थ नहीं होगा।

और ज्यादा उदाहरण

  • ओ (1) = ओ (एन) = ओ (एन 2 ) जब एन → + ∞ (लेकिन दूसरी तरफ नहीं, समानता "नकली" है),

  • ओ (एन) + ओ (एन 2 ) = ओ (एन 2 ) जब एन → + ∞

  • ओ (ओ (एन 2 )) = ओ (एन 2 ) जब एन → + ∞

  • ओ (एन 2 ) ओ (एन 3 ) = ओ (एन 5 ) जब एन → + ∞

विकिपीडिया लेख यहां है: https://en.wikipedia.org/wiki/Big_O_notation


यहां बिग-ओ की सामान्य किस्में बताते समय सादा अंग्रेजी सहायक है जिसका उपयोग मैं करता हूं

सभी मामलों में, सूची में निचले लोगों को सूची में एल्गोरिदम अधिक पसंद करते हैं। हालांकि, एक और महंगी जटिलता कक्षा में जाने की लागत में काफी भिन्नता है।

हे (1):

कोई विकास नहीं। इस समस्या के बावजूद कि समस्या कितनी बड़ी है, आप इसे उसी समय में हल कर सकते हैं। यह प्रसारित करने के लिए कुछ हद तक समान है जहां प्रसारण सीमा के भीतर मौजूद लोगों की संख्या के बावजूद, किसी दिए गए दूरी पर प्रसारित करने के लिए समान मात्रा में ऊर्जा लेती है।

ओ (लॉग एन ):

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

ओ ( एन ):

समस्या को हल करने की लागत समस्या के आकार के समान है। यदि आपकी समस्या आकार में दोगुना हो जाती है, तो समाधान की लागत दोगुना हो जाती है। चूंकि अधिकांश समस्याओं को कंप्यूटर में स्कैन किया जाना है, क्योंकि डेटा एंट्री, डिस्क पढ़ता है, या नेटवर्क ट्रैफिक होता है, यह आमतौर पर एक किफायती स्केलिंग कारक होता है।

हे ( एन लॉग एन ):

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

ओ ( एन 2 ):

एक वर्ग के रूप में बढ़ता है, जहां एन वर्ग के किनारे की लंबाई है। यह "विकास प्रभाव" के समान विकास दर है, जहां नेटवर्क में हर कोई नेटवर्क में हर किसी को जानता है। विकास महंगा है। अधिकांश स्केलेबल समाधान महत्वपूर्ण जिमनास्टिक किए बिना जटिलता के इस स्तर के साथ एल्गोरिदम का उपयोग नहीं कर सकते हैं। यह आम तौर पर अन्य सभी बहुपद जटिलताओं - ओ ( एन के ) पर भी लागू होता है - साथ ही।

ओ (2 एन ):

स्केल नहीं करता है। आपको किसी भी गैर-मामूली आकार की समस्या को हल करने की कोई उम्मीद नहीं है। क्या बचाना है, और विशेषज्ञों के लिए ओ ( एन के ) में अनुमानित एल्गोरिदम खोजने के लिए उपयोगी है ।


निश्चित नहीं है कि मैं इस विषय में आगे योगदान कर रहा हूं लेकिन अभी भी सोचा था कि मैं साझा करूंगा: मुझे एक बार यह ब्लॉग पोस्ट कुछ बिग ओ पर कुछ उपयोगी (हालांकि बहुत बुनियादी) स्पष्टीकरण और उदाहरण प्राप्त करने के लिए मिला:

उदाहरणों के माध्यम से, इससे मेरी कछुए की तरह खोपड़ी में नंगे मूल बातें प्राप्त करने में मदद मिली, इसलिए मुझे लगता है कि यह सही दिशा में जाने के लिए 10 मिनट का एक सुंदर वंश है।


संपादित करें: त्वरित नोट, यह थैटा नोटेशन (जो ऊपरी और निचले बाउंड दोनों है) के साथ बिग ओ नोटेशन (जो ऊपरी बाउंड है) को लगभग निश्चित रूप से भ्रमित कर रहा है। मेरे अनुभव में यह वास्तव में गैर-शैक्षणिक सेटिंग्स में चर्चाओं की विशिष्टता है। किसी भी भ्रम के लिए क्षमा चाहते हैं।

एक वाक्य में: जैसे ही आपका काम बढ़ता है, इसे पूरा करने में कितना समय लगता है?

स्पष्ट रूप से यह केवल इनपुट के रूप में "आकार" का उपयोग कर रहा है और आउटपुट के रूप में "समय लिया गया" - वही विचार लागू होता है यदि आप स्मृति उपयोग आदि के बारे में बात करना चाहते हैं।

यहां एक उदाहरण दिया गया है जहां हमारे पास एन टी-शर्ट हैं जिन्हें हम सूखना चाहते हैं। हम उन्हें सूखने की स्थिति में लाने के लिए अविश्वसनीय रूप से जल्दी मानेंगे (यानी मानव बातचीत नगण्य है)। वास्तविक जीवन में यह मामला नहीं है, ज़ाहिर है ...

  • बाहर एक वाशिंग लाइन का उपयोग करना: मान लीजिए कि आपके पास असीमित रूप से बड़ा बैक यार्ड है, ओ (1) समय में धुलाई धो रही है। हालांकि आपके पास बहुत कुछ है, यह वही सूरज और ताजा हवा प्राप्त करेगा, इसलिए आकार सुखाने के समय को प्रभावित नहीं करता है।

  • टम्बल ड्रायर का उपयोग करना: आप प्रत्येक भार में 10 शर्ट डालते हैं, और फिर वे एक घंटे बाद किए जाते हैं। (यहां वास्तविक संख्याओं को अनदेखा करें - वे अप्रासंगिक हैं।) इसलिए 50 शर्ट सूखने से लगभग 5 गुना सूखने तक 5 गुना होता है।

  • एक एयरिंग अलमारी में सबकुछ डाल देना: अगर हम सब कुछ एक बड़े ढेर में डालते हैं और सामान्य गर्मी को करते हैं, तो मध्यम शर्ट को सूखने में काफी समय लगेगा। मैं विस्तार से अनुमान लगाने की इच्छा नहीं रखूंगा, लेकिन मुझे संदेह है कि यह कम से कम ओ (एन ^ 2) है - जैसे ही आप धोने के भार को बढ़ाते हैं, सुखाने का समय तेजी से बढ़ता है।

"बड़े ओ" नोटेशन का एक महत्वपूर्ण पहलू यह है कि यह नहीं कहता कि दिए गए आकार के लिए कौन सा एल्गोरिदम तेज होगा। जोड़ों की एक सरणी (स्ट्रिंग, पूर्णांक) बनाम हैशटेबल (स्ट्रिंग कुंजी, पूर्णांक मान) लें। क्या स्ट्रिंग के आधार पर हैशटेबल या सरणी में तत्व में कोई कुंजी ढूंढना तेज़ है? (यानी सरणी के लिए, "पहला तत्व ढूंढें जहां स्ट्रिंग भाग दिए गए कुंजी से मेल खाता है।") हैशटेबल्स आम तौर पर अमूर्त (~ = "औसतन") ओ (1) होते हैं - एक बार जब वे सेट हो जाते हैं, तो इसे लेना चाहिए 1,000,000 प्रविष्टि तालिका में 100 प्रविष्टि तालिका में प्रवेश प्राप्त करने के लिए एक ही समय। किसी सरणी (इंडेक्स की बजाय सामग्री के आधार पर) में तत्व ढूंढना रैखिक है, यानी ओ (एन) - औसतन, आपको आधे प्रविष्टियों को देखना होगा।

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


बिग ओ के एक सादे अंग्रेजी स्पष्टीकरण क्या है? यथासंभव सरल और सरल गणित के रूप में छोटी औपचारिक परिभाषा के साथ।

बिग-ओ नोटेशन की आवश्यकता का एक सादा अंग्रेजी स्पष्टीकरण :

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

का एक सादा अंग्रेजी स्पष्टीकरण क्या बिग ओ संकेतन है:

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


इसे देखने का सबसे आसान तरीका (सादे अंग्रेजी में)

हम यह देखने की कोशिश कर रहे हैं कि इनपुट पैरामीटर की संख्या, एल्गोरिदम के चलने वाले समय को कैसे प्रभावित करती है। यदि आपके आवेदन का चलने का समय इनपुट पैरामीटर की संख्या के समान है, तो यह एन के बिग ओ में कहा जाता है।

उपरोक्त कथन एक अच्छी शुरुआत है लेकिन पूरी तरह से सच नहीं है।

एक और सटीक स्पष्टीकरण (गणितीय)

मान लीजिए

एन = इनपुट पैरामीटर की संख्या

टी (एन) = वास्तविक कार्य जो ए के एक समारोह के रूप में एल्गोरिदम के चलने का समय व्यक्त करता है

सी = एक स्थिर

एफ (एन) = एक अनुमानित कार्य जो ए के एक समारोह के रूप में एल्गोरिदम के चलने का समय व्यक्त करता है

तब तक जहां तक ​​बिग ओ का संबंध है, अनुमानित एफ (एन) तब तक पर्याप्त माना जाता है जब तक कि नीचे की स्थिति सही न हो।

lim     T(n) ≤ c×f(n)
n→∞

समीकरण को पढ़ा जाता है क्योंकि एन एन अनंतता तक पहुंचता है, एन का टी, एन के सी गुणा एफ से कम या बराबर होता है।

बड़े ओ नोटेशन में यह लिखा गया है

T(n)∈O(n)

यह पढ़ा जाता है क्योंकि टी का एन एन के बड़े ओ में है।

वापस अंग्रेजी में

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

एन का बिग ओ मतलब है कि मेरा एल्गोरिदम कम से कम जितना तेज़ चलता है। आप अपने एल्गोरिदम के बिग ओ नोटेशन को नहीं देख सकते हैं और इसकी धीमी गति से कह सकते हैं। आप केवल तेज़ कह सकते हैं।

यूसी बर्कले से बिग ओ पर एक वीडियो ट्यूटोरियल के लिए this देखें । यह वास्तव में एक साधारण अवधारणा है। यदि आप प्रोफेसर शेवचक (उर्फ भगवान स्तर के शिक्षक) को समझाते हैं, तो आप कहेंगे "ओह यह सब कुछ है!"।


"बिग ओ" नोटेशन का सादा अंग्रेजी स्पष्टीकरण क्या है?

बहुत तेज़ नोट:

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

  • "बिग ओ" दो चीजें करता है:

    1. अनुमान लगाता है कि कार्य पूरा करने के लिए आपका कंप्यूटर किस विधि पर लागू होता है।
    2. यह निर्धारित करने के लिए कि क्या यह अच्छा है या नहीं, प्रक्रियाओं को दूसरों के साथ तुलना करने के लिए सुविधा प्रदान करें?
    3. "बिग ओ 'मानकीकृत के साथ उपर्युक्त दो प्राप्त करता है Notations
  • सात सबसे अधिक उपयोग किए गए नोटेशन हैं

    1. ओ (1), इसका मतलब है कि आपके कंप्यूटर को 1चरण के साथ एक कार्य मिलता है , यह उत्कृष्ट है, आदेश दिया गया नंबर 1
    2. ओ (लॉगएन), इसका मतलब है कि आपका कंप्यूटर logNचरणों के साथ एक कार्य पूरा करता है , इसका अच्छा, आदेश संख्या 2
    3. ओ (एन), Nचरणों के साथ एक कार्य खत्म करें, इसके मेले, आदेश संख्या 3
    4. ओ (एनएलओएनएन), O(NlogN)चरणों के साथ एक कार्य समाप्त करता है , यह अच्छा नहीं है, आदेश संख्या 4
    5. ओ (एन ^ 2), N^2चरणों के साथ एक काम मिलता है , यह बुरा है, आदेश संख्या 5
    6. ओ (2 ^ एन), 2^Nचरणों के साथ एक काम मिलता है , यह भयानक है, आदेश संख्या 6
    7. हे (एन!), N!कदमों के साथ एक काम मिलता है , यह भयानक है, आदेश संख्या 7

मान लीजिए कि आपको नोटेशन मिलता है O(N^2), न केवल आप स्पष्ट हैं कि विधि को कार्य पूरा करने के लिए एन * एन कदम उठाते हैं, आप यह भी देखते हैं कि यह O(NlogN)इसकी रैंकिंग से अच्छा नहीं है ।

कृपया अपनी बेहतर समझ के लिए लाइन अंत में ऑर्डर नोट करें। यदि सभी संभावनाओं पर विचार किया जाता है तो 7 से अधिक नोटेशन हैं।

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

इसके अलावा, बिग ओ सबसे बुरी स्थिति स्थापित करता है या ऊपरी-बाउंड चरणों को मापता है।
आप सबसे अच्छे मामले के लिए बिग-Ω (बिग-ओमेगा) का उल्लेख कर सकते हैं।

बिग-Ω (बिग-ओमेगा) नोटेशन (लेख) | खान अकादमी

  • सारांश
    "बिग ओ" एल्गोरिदम के प्रदर्शन का वर्णन करता है और इसका मूल्यांकन करता है।

    या इसे औपचारिक रूप से संबोधित करें, "बिग ओ" एल्गोरिदम वर्गीकृत करता है और तुलना प्रक्रिया को मानकीकृत करता है।


एक सरल सीधा जवाब हो सकता है:

बिग ओ उस एल्गोरिदम के लिए सबसे खराब संभव समय / स्थान का प्रतिनिधित्व करता है। एल्गोरिदम कभी भी उस सीमा से अधिक स्थान / समय नहीं लेगा। बिग ओ चरम मामले में समय / अंतरिक्ष जटिलता का प्रतिनिधित्व करता है।


परिभाषा: - बिग ओ नोटेशन एक संकेत है जो कहता है कि डेटा इनपुट बढ़ने पर एल्गोरिदम प्रदर्शन कैसे करेगा।

जब हम एल्गोरिदम के बारे में बात करते हैं तो 3 महत्वपूर्ण खंभे इनपुट, आउटपुट और एल्गोरिदम की प्रसंस्करण होते हैं। बिग ओ प्रतीकात्मक नोटेशन है जो कहता है कि डेटा इनपुट में वृद्धि हुई है, जिसमें एल्गोरिदम प्रोसेसिंग के प्रदर्शन में कितनी दर होगी।

मैं आपको इस यूट्यूब वीडियो को देखने के लिए प्रोत्साहित करता हूं जो कोड उदाहरणों के साथ गहराई में बिग ओ नोटेशन बताता है ।

तो उदाहरण के लिए मान लें कि एक एल्गोरिदम में 5 रिकॉर्ड होते हैं और प्रोसेसिंग के लिए आवश्यक समय 27 सेकंड होता है। अब अगर हम 10 को रिकॉर्ड बढ़ाते हैं तो एल्गोरिदम 105 सेकंड लेता है।

सरल शब्दों में लिया गया समय रिकॉर्ड की संख्या का वर्ग है। हम ओ (एन ^ 2) द्वारा इसका उल्लेख कर सकते हैं । इस प्रतीकात्मक प्रतिनिधित्व को बिग ओ नोटेशन कहा जाता है।

अब कृपया ध्यान दें कि इकाइयां इनपुट में कुछ भी हो सकती हैं, यह बाइट्स हो सकती है, बिट्स रिकॉर्ड की संख्या, प्रदर्शन किसी भी इकाई में दूसरे, मिनट, दिन आदि जैसे मापा जा सकता है। तो यह सटीक इकाई नहीं बल्कि बल्कि रिश्ते है।

उदाहरण के लिए नीचे दिए गए फ़ंक्शन "फंक्शन 1" को देखें जो संग्रह लेता है और पहले रिकॉर्ड पर प्रोसेसिंग करता है। अब इस समारोह के लिए प्रदर्शन 1000, 10000 या 100000 रिकॉर्ड रखे बिना भी वही होगा। तो हम इसे ओ (1) द्वारा इंगित कर सकते हैं ।

void Function1(List<string> data)
{
string str = data[0];
}

अब नीचे दिए गए फ़ंक्शन "फ़ंक्शन 2 ()" देखें। इस मामले में प्रसंस्करण समय रिकॉर्ड की संख्या के साथ बढ़ेगा। हम ओ (एन) का उपयोग करके इस एल्गोरिदम प्रदर्शन को दर्शा सकते हैं ।

void Function2(List<string> data)
        {
            foreach(string str in data)
            {
                if (str == "shiv")
                {
                    return;
                }
            }
        }

जब हम किसी भी एल्गोरिदम के लिए बिग ओ नोटेशन देखते हैं तो हम उन्हें प्रदर्शन की तीन श्रेणियों में वर्गीकृत कर सकते हैं: -

  1. लॉग और निरंतर श्रेणी: - कोई भी डेवलपर इस श्रेणी में अपने एल्गोरिदम प्रदर्शन को देखना पसंद करेगा।
  2. रैखिक: - डेवलपर इस श्रेणी में एल्गोरिदम नहीं देखना चाहता, जब तक कि उसका अंतिम विकल्प या एकमात्र विकल्प शेष न हो जाए।
  3. घातीय: - यह वह जगह है जहां हम अपने एल्गोरिदम नहीं देखना चाहते हैं और एक पुनर्विक्रय की आवश्यकता है।

तो बिग ओ नोटेशन को देखकर हम एल्गोरिदम के लिए अच्छे और बुरे जोनों को वर्गीकृत करते हैं।

मैं आपको इस 10 मिनट के वीडियो को देखने की सलाह दूंगा जो नमूना कोड के साथ बिग ओ पर चर्चा करता है

https://www.youtube.com/watch?v=k6kxtzICG_g


" बिग ओ की एक सादे अंग्रेजी व्याख्या क्या है? जितनी कम औपचारिक परिभाषा संभव और सरल गणित के रूप में। "

इस तरह का एक सुंदर सरल और छोटा सवाल कम से कम एक छोटे से जवाब के लायक होने के लिए लगता है, जैसे छात्र को ट्यूशन के दौरान प्राप्त हो सकता है।

बिग ओ नोटेशन बस बताता है कि इनपुट डेटा की मात्रा के संदर्भ में कितना समय * एक एल्गोरिदम चलाया जा सकता है **।

(* एक अद्भुत, यूनिट-मुक्त समय में!)
(** जो मायने रखता है, क्योंकि लोग हमेशा और अधिक चाहते हैं , चाहे वे आज या कल रहें)

खैर, बिग ओ नोटेशन के बारे में इतना बढ़िया क्या है अगर ऐसा ही होता है?

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

  • बिग ओ नोटेशन कंप्यूटर प्रोग्रामिंग / इंजीनियरिंग के सबसे महत्वपूर्ण सिद्धांत पर सीधे स्पॉटलाइट को चमकता है, यह तथ्य जो सभी अच्छे प्रोग्रामर को सोचने और सपने देखने के लिए प्रेरित करता है: प्रौद्योगिकी के धीमे आगे मार्च से परे परिणाम प्राप्त करने का एकमात्र तरीका बेहतर आविष्कार करना है एल्गोरिदम


बिग ओ एक सामान्य तरीके से स्वयं को "एक्सप्रेस" करने का एक तरीका है, "मेरे कोड को चलाने के लिए कितना समय / स्थान लगता है?"।

आप अक्सर ओ (एन), ओ (एन 2 ), ओ (nlogn) और आगे देख सकते हैं, ये सभी दिखाने के लिए सिर्फ तरीके हैं; एल्गोरिदम कैसे बदलता है?

ओ (एन) का मतलब है बिग ओ एन है, और अब आप सोच सकते हैं, "एन क्या है ??" खैर "एन" तत्वों की मात्रा है। इमेजिंग आप एक ऐरे में एक आइटम खोजना चाहते हैं। आपको प्रत्येक तत्व को देखना होगा और "क्या आप सही तत्व / वस्तु हैं?" सबसे बुरे मामले में, आइटम अंतिम सूचकांक में है, जिसका अर्थ है कि सूची में वस्तुओं के रूप में उतना समय लगता है, इसलिए सामान्य होने के लिए, हम कहते हैं, "अरे हे, एन उचित मूल्य है!" ।

तो फिर आप समझ सकते हैं कि "एन 2 " का अर्थ क्या है, लेकिन इससे भी अधिक विशिष्ट होने के लिए, सोचा कि आपके पास एक सरल, सॉर्टिंग एल्गोरिदम का सबसे सरल है; बबल शॅाट। प्रत्येक एल्गोरिदम को प्रत्येक आइटम के लिए पूरी सूची देखने की आवश्यकता है।

मेरी सूची

  1. 1
  2. 6
  3. 3

यहां प्रवाह होगा:

  • 1 और 6 की तुलना करें, जो सबसे बड़ा है? ठीक है 6 सही स्थिति में है, आगे बढ़ रहा है!
  • 6 और 3 की तुलना करें, ओह, 3 कम है! आइए इसे ले जाएं, ठीक है सूची बदल गई है, हमें शुरुआत से ही शुरुआत करने की ज़रूरत है!

यह ओ एन 2 है क्योंकि, आपको सूची में सभी वस्तुओं को देखने की आवश्यकता है "एन" आइटम हैं। प्रत्येक आइटम के लिए, आप एक बार फिर सभी वस्तुओं को देखते हैं, तुलना करने के लिए, यह भी "एन" है, इसलिए प्रत्येक आइटम के लिए, आप "n" बार देखते हैं जिसका अर्थ है n * n = n 2

मुझे उम्मीद है कि यह उतना आसान है जितना आप चाहते हैं।

लेकिन याद रखें, बिग ओ समय और स्थान के तरीके में खुद को फैलाने का एक तरीका है।


सॉफ्टवेयर कार्यक्रमों की गति को मापना बहुत मुश्किल है, और जब हम कोशिश करते हैं, तो उत्तर बहुत जटिल हो सकते हैं और अपवादों और विशेष मामलों से भरे जा सकते हैं। यह एक बड़ी समस्या है, क्योंकि उन सभी अपवादों और विशेष मामलों में विचलित और अनुपयोगी हैं जब हम एक दूसरे के साथ दो अलग-अलग कार्यक्रमों की तुलना करना चाहते हैं ताकि यह पता चल सके कि "सबसे तेज़" कौन सा है।

इस असहनीय जटिलता के परिणामस्वरूप, लोग सबसे छोटे और कम से कम जटिल (गणितीय) अभिव्यक्तियों का उपयोग करके सॉफ्टवेयर प्रोग्राम की गति का वर्णन करने का प्रयास करते हैं। ये अभिव्यक्ति बहुत ही क्रूर अनुमान हैं: हालांकि, कुछ भाग्य के साथ, वे "सार" पर कब्जा करेंगे कि सॉफ्टवेयर का एक टुकड़ा तेज़ या धीमा है या नहीं।

क्योंकि वे अनुमान हैं, हम अभिव्यक्ति में "ओ" (बिग ओह) पत्र का उपयोग करते हैं, एक पाठक को संकेत देते हैं कि हम सकल oversimplification बना रहे हैं। (और यह सुनिश्चित करने के लिए कि कोई भी गलती से सोचता है कि अभिव्यक्ति किसी भी तरह सटीक नहीं है)।

यदि आप "ओह" या "लगभग" के अर्थ के रूप में "ओह" पढ़ते हैं तो आप बहुत गलत नहीं होंगे। (मुझे लगता है कि बिग-ओह की पसंद हास्य का प्रयास हो सकती है)।

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

अच्छा:

  • O(1) निरंतर : कार्यक्रम चलाने के लिए एक ही समय लगता है इससे कोई फर्क नहीं पड़ता कि इनपुट कितना बड़ा है।
  • O(log n) लॉगरिदमिक : प्रोग्राम रन-टाइम इनपुट के आकार में बड़ी वृद्धि के साथ भी धीरे-धीरे बढ़ता है।

खराब:

  • O(n) रैखिक : प्रोग्राम रन-टाइम इनपुट के आकार के अनुपात में आनुपातिक रूप से बढ़ता है।
  • O(n^k) बहुपद : - प्रसंस्करण का समय तेजी से और तेज़ी से बढ़ता है - एक बहुपद कार्य के रूप में - इनपुट के आकार के रूप में बढ़ता है।

... और बदसूरत:

  • O(k^n) घातीय कार्यक्रम समस्या के आकार में भी मध्यम वृद्धि के साथ कार्यक्रम रन-टाइम बहुत तेजी से बढ़ता है - यह केवल एक्सोनोनेंशियल एल्गोरिदम के साथ छोटे डेटा सेट को संसाधित करने के लिए व्यावहारिक है।
  • O(n!) फैक्टोरियल कार्यक्रम रन-टाइम लंबे समय से अधिक होगा, लेकिन आप किसी भी चीज़ के लिए इंतजार कर सकते हैं, लेकिन सबसे छोटे और सबसे छोटे-दिखने वाले डेटासेट।

ठीक है, मेरे 2 सेंट।

बिग-ओ, प्रोग्राम द्वारा खपत संसाधनों की वृद्धि दर है , wrt समस्या-उदाहरण-आकार

संसाधन: कुल-सीपीयू समय हो सकता है, अधिकतम रैम स्पेस हो सकता है। डिफ़ॉल्ट रूप से CPU समय को संदर्भित करता है।

कहें समस्या "योग खोजें" है,

int Sum(int*arr,int size){
      int sum=0;
      while(size-->0) 
         sum+=arr[size]; 

      return sum;
}

समस्या-उदाहरण = {5,10,15} ==> समस्या-उदाहरण-आकार = 3, पुनरावृत्तियों-इन-लूप = 3

समस्या-उदाहरण = {5,10,15,20,25} ==> समस्या-उदाहरण-आकार = 5 पुनरावृत्तियों-इन-लूप = 5

आकार "एन" के इनपुट के लिए प्रोग्राम सरणी में "एन" पुनरावृत्तियों की गति से बढ़ रहा है। इसलिए बिग-ओ एन को ओ (एन) के रूप में व्यक्त किया गया है

कहें समस्या "संयोजन खोजें" है,

    void Combination(int*arr,int size)
    { int outer=size,inner=size;
      while(outer -->0) {
        inner=size;
        while(inner -->0)
          cout<<arr[outer]<<"-"<<arr[inner]<<endl;
      }
    }

समस्या-उदाहरण = {5,10,15} ==> समस्या-उदाहरण-आकार = 3, कुल-पुनरावृत्तियों = 3 * 3 = 9

समस्या-उदाहरण = {5,10,15,20,25} ==> समस्या-उदाहरण-आकार = 5, कुल-पुनरावृत्तियों = 5 * 5 = 25

आकार "एन" के इनपुट के लिए प्रोग्राम सरणी में "एन * एन" पुनरावृत्तियों की गति से बढ़ रहा है। इसलिए बिग-ओ एन 2 को ओ (एन 2 ) के रूप में व्यक्त किया गया है


बिग ओ नोटेशन यह वर्णन करने का एक तरीका है कि एल्गोरिदम कितनी तेज़ी से इनपुट पैरामीटर की मनमानी संख्या प्रदान करेगा, जिसे हम "n" कहते हैं। यह कंप्यूटर विज्ञान में उपयोगी है क्योंकि विभिन्न मशीनें अलग-अलग गति से संचालित होती हैं, और बस यह कहती हैं कि एक एल्गोरिदम 5 सेकंड लेता है, आपको बहुत कुछ नहीं बताता है क्योंकि जब आप 4.5 गीगा ऑक्टो-कोर प्रोसेसर वाला सिस्टम चला रहे हैं, तो मैं दौड़ सकता हूं एक 15 वर्षीय, 800 मेगाहर्ट्ज सिस्टम, जो एल्गोरिदम के बावजूद अधिक समय ले सकता है। तो यह निर्दिष्ट करने के बजाय कि समय के संदर्भ में एल्गोरिदम कितनी तेजी से चलता है, हम कहते हैं कि यह इनपुट पैरामीटर की संख्या या "एन" के संदर्भ में कितनी तेज़ी से चलता है। इस तरह से एल्गोरिदम का वर्णन करके, हम कंप्यूटर की गति को ध्यान में रखे बिना एल्गोरिदम की गति की तुलना करने में सक्षम हैं।


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

जब हम कहते हैं कि कुछ एल्गोरिदम ओ (एफ (एन) है) हम कह रहे हैं कि उस एल्गोरिदम द्वारा चलने वाला समय (या स्थान आवश्यक) हमेशा कुछ स्थिर समय एफ (एन) से कम होता है।

यह कहने के लिए कि बाइनरी खोज में ओ (लॉगऑन) का चलने का समय है, यह कहना है कि कुछ स्थिर सी मौजूद है जो आप लॉग (एन) गुणा कर सकते हैं, यह हमेशा बाइनरी खोज के चलने वाले समय से बड़ा होगा। इस मामले में आप हमेशा लॉग (एन) तुलना के कुछ स्थिर कारक होगा।

दूसरे शब्दों में जहां जी (एन) आपके एल्गोरिदम का चलने का समय है, हम कहते हैं कि जी (एन) = ओ (एफ (एन)) जब जी (एन) <= ​​सी * एफ (एन) जब n> k, जहां सी और के कुछ स्थिरांक हैं।


मान लें कि हैरी पॉटर ऑर्डर करें: अमेज़ॅन से 8-फिल्म संग्रह [ब्लू-रे] पूर्ण करें और एक ही समय में एक ही फिल्म संग्रह ऑनलाइन डाउनलोड करें। आप जांचना चाहते हैं कि कौन सी विधि तेज है। डिलीवरी आने के लिए लगभग एक दिन लगती है और डाउनलोड लगभग 30 मिनट पहले पूरा हो जाता है। महान! तो यह एक तंग दौड़ है।

क्या होगा यदि मैं कई ब्लू-रे फिल्मों जैसे द लॉर्ड ऑफ द रिंग्स, ट्वाइलाइट, द डार्क नाइट त्रयी आदि का ऑर्डर करता हूं और एक ही समय में सभी फिल्में ऑनलाइन डाउनलोड करता हूं? इस बार, डिलीवरी अभी भी पूरा होने में एक दिन लगती है, लेकिन ऑनलाइन डाउनलोड को समाप्त होने में 3 दिन लगते हैं। ऑनलाइन खरीदारी के लिए, खरीदे गए आइटम (इनपुट) की संख्या प्रसव के समय को प्रभावित नहीं करती है। आउटपुट स्थिर है। हम इसे ओ (1) कहते हैं

ऑनलाइन डाउनलोड करने के लिए, डाउनलोड समय मूवी फ़ाइल आकार (इनपुट) के लिए सीधे आनुपातिक है। हम इसे ओ (एन) कहते हैं

प्रयोगों से, हम जानते हैं कि ऑनलाइन शॉपिंग स्केल ऑनलाइन डाउनलोड से बेहतर है। बड़े ओ नोटेशन को समझना बहुत महत्वपूर्ण है क्योंकि यह आपको एल्गोरिदम की स्केलेबिलिटी और दक्षता का विश्लेषण करने में मदद करता है।

नोट: बिग ओ नोटेशन एल्गोरिदम के सबसे खराब-केस परिदृश्य का प्रतिनिधित्व करता है। आइए मान लें कि ओ (1) और ओ (एन) ऊपर दिए गए उदाहरण के सबसे बुरे मामले परिदृश्य हैं।

संदर्भ : http://carlcheo.com/compsci


बिग-ओ नोटेशन (जिसे "एसिम्प्टोटिक ग्रोथ" नोटेशन भी कहा जाता है) जब आप लगातार कारकों और मूल के आस-पास की चीजों को अनदेखा करते हैं तो "जैसा दिखता है" कार्य करता है । हम इसका उपयोग कैसे करें पैमाने के बारे में बात करने के लिए करते हैं।

मूल बातें

"पर्याप्त" बड़े इनपुट के लिए ...

  • f(x) ∈ O(upperbound) मतलब है f " upperbound से तेज नहीं upperbound
  • f(x) ∈ Ɵ(justlikethis) मतलब है f "ठीक तरह से बढ़ता है" justlikethis
  • f(x) ∈ Ω(lowerbound) मतलब है f " lowerbound से धीमा नहीं होता है"

बड़े-ओ नोटेशन निरंतर कारकों की परवाह नहीं करता है: फ़ंक्शन 9x² को "ठीक तरह से बढ़ने" कहा जाता है। गैर-एसिम्प्टोटिक सामग्री ("मूल के पास सामान" या "समस्या का आकार छोटा होने पर क्या होता है" के बारे में बड़ी-ओ एसिम्प्टोटिक नोटेशन देखभाल नहीं करता है: फ़ंक्शन 10x² को "ठीक तरह से बढ़ने" कहा जाता है 10x² - x + 2

आप समीकरण के छोटे हिस्सों को क्यों नजरअंदाज करना चाहते हैं? क्योंकि वे समीकरण के बड़े हिस्सों से पूरी तरह से बौने हो जाते हैं क्योंकि आप बड़े और बड़े पैमाने पर विचार करते हैं; उनका योगदान बौना और अप्रासंगिक हो जाता है। (उदाहरण खंड देखें।)

एक और तरीका रखो, यह अनुपात के बारे में है जब आप अनंत तक जाते हैं। यदि आप O(...) द्वारा वास्तविक समय को विभाजित करते हैं, तो आपको बड़े इनपुट की सीमा में निरंतर कारक मिल जाएगा। सहजता से यह समझ में आता है: यदि आप दूसरे को प्राप्त करने के लिए एक को गुणा कर सकते हैं तो "एक जैसे" पैमाने पर कार्य करें। यही है, जब हम कहते हैं ...

actualAlgorithmTime(N) ∈ O(bound(N))
                                       e.g. "time to mergesort N elements 
                                             is O(N log(N))"

... इसका मतलब है कि "बड़ी पर्याप्त" समस्या के आकार एन (यदि हम मूल के पास सामानों को अनदेखा करते हैं) के लिए, कुछ निरंतर मौजूद हैं (जैसे 2.5, पूरी तरह से बनाया गया) जैसे कि:

actualAlgorithmTime(N)                 e.g. "mergesort_duration(N)       "
────────────────────── < constant            ───────────────────── < 2.5 
       bound(N)                                    N log(N)         

निरंतर कई विकल्प हैं; प्रायः "सर्वश्रेष्ठ" विकल्प को एल्गोरिदम के "निरंतर कारक" के रूप में जाना जाता है ... लेकिन हम अक्सर इसे अनदेखा करते हैं जैसे कि हम गैर-सबसे बड़े शब्दों को अनदेखा करते हैं (वे लगातार कारक क्यों नहीं देखते हैं) के लिए लगातार कारक अनुभाग देखें। आप उपरोक्त समीकरण को बाध्य के रूप में भी सोच सकते हैं, " सबसे बुरी स्थिति परिदृश्य में, जो समय लगता है वह लगभग 2.5 * के कारक के भीतर लगभग N*log(N) से भी बदतर नहीं होगा (एक स्थिर कारक हम नहीं करते हैं ' टी के बारे में ज्यादा परवाह नहीं है) "।

आम तौर पर, O(...) सबसे उपयोगी है क्योंकि हम अक्सर सबसे बुरी स्थिति के व्यवहार की परवाह करते हैं। यदि f(x) प्रोसेसर या मेमोरी उपयोग जैसे कुछ "खराब" का प्रतिनिधित्व करता है, तो " f(x) ∈ O(upperbound) " का अर्थ है " upperbound प्रोसेसर / मेमोरी उपयोग का सबसे खराब केस परिदृश्य है"।

अनुप्रयोगों

पूरी तरह से गणितीय निर्माण के रूप में, बड़े-ओ नोटेशन समय और स्मृति प्रसंस्करण के बारे में बात करने तक ही सीमित नहीं है। आप इसका उपयोग किसी भी चीज के एसिम्प्टोटिक्स पर चर्चा करने के लिए कर सकते हैं जहां स्केलिंग सार्थक है, जैसे कि:

  • एक पार्टी ( Ɵ(N²) , विशेष रूप से N(N-1)/2 में N लोगों के बीच संभवतः हैंडशेक की संख्या, लेकिन क्या मायने रखता है कि यह " तरह" )
  • उन लोगों की संभाव्य अपेक्षित संख्या जिन्होंने कुछ समय के कार्य के रूप में कुछ वायरल मार्केटिंग देखा है
  • सीपीयू या जीपीयू या कंप्यूटर क्लस्टर में प्रसंस्करण इकाइयों की संख्या के साथ वेबसाइट विलंबता स्केल कैसे करें
  • सीपीयू पर गर्मी आउटपुट स्केल कैसे ट्रांजिस्टर गिनती, वोल्टेज इत्यादि के एक समारोह के रूप में मर जाता है।
  • इनपुट आकार के एक समारोह के रूप में, एल्गोरिदम को कितना समय चलाने की आवश्यकता है
  • इनपुट आकार के एक समारोह के रूप में, एल्गोरिदम को कितनी जगह चलाने की आवश्यकता है

उदाहरण

ऊपर हैंडशेक उदाहरण के लिए, कमरे में हर कोई हर किसी के हाथ हिलाता है। उस उदाहरण में, #handshakes ∈ Ɵ(N²) । क्यूं कर?

थोड़ा सा बैक अप लें: हैंडशेक की संख्या बिल्कुल एन-चयन -2 या N*(N-1)/2 (एन में से प्रत्येक व्यक्ति एन -1 अन्य लोगों के हाथ हिलाता है, लेकिन यह डबल-गिनती हैंडशेक तो विभाजित करते हैं 2):

हालांकि, बहुत बड़ी संख्या में लोगों के लिए, रैखिक शब्द N बौना होता है और प्रभावी रूप से अनुपात में 0 योगदान देता है (चार्ट में: कुल बक्से पर विकर्ण पर खाली बक्से का अंश छोटा हो जाता है क्योंकि प्रतिभागियों की संख्या बड़ी हो जाती है)। इसलिए स्केलिंग व्यवहार order N² , या हैंडशेक की संख्या "एन² की तरह बढ़ती है"।

#handshakes(N)
────────────── ≈ 1/2
     N²

ऐसा लगता है कि चार्ट के विकर्ण पर खाली बक्से (एन * (एन -1) / 2 चेकमार्क) वहां भी नहीं थे (एन 2 चेकमार्क असम्बद्ध रूप से)।

("सादे अंग्रेजी" से अस्थायी digression :) यदि आप इसे अपने आप को साबित करना चाहते हैं, तो आप इसे अनुपात में कुछ सरल बीजगणित कर सकते हैं ताकि इसे कई शर्तों में विभाजित किया जा सके ( lim मतलब है "की सीमा में माना जाता है", बस इसे अनदेखा करें आपने इसे नहीं देखा है, यह सिर्फ "और एन वास्तव में बड़ा है" के लिए नोटेशन है:):

    N²/2 - N/2         (N²)/2   N/2         1/2
lim ────────── = lim ( ────── - ─── ) = lim ─── = 1/2
N→∞     N²       N→∞     N²     N²      N→∞  1
                               ┕━━━┙
             this is 0 in the limit of N→∞:
             graph it, or plug in a really large number for N

टीएल; डॉ: हैंडशेक की संख्या 'x² जैसी बड़ी मानों के लिए बहुत अधिक दिखती है, कि अगर हम अनुपात # हैंडशेक / एक्स² लिखना चाहते थे, तो तथ्य यह है कि हमें बिल्कुल x² हैंडशेक की आवश्यकता नहीं है एक मनमाने ढंग से बड़े समय के लिए दशमलव में।

उदाहरण के लिए एक्स = 1 मिलियन, अनुपात # हैंडशेक / एक्स²: 0.4 99 999 ...

अंतर्निहित बिल्डिंग

यह हमें बयान देने देता है ...

"बड़े पर्याप्त इनपुट आकार = एन के लिए, कोई फर्क नहीं पड़ता कि निरंतर कारक क्या है, अगर मैं इनपुट आकार को दोगुना करता हूं ...

  • ... मैं समय ओ (एन) ("रैखिक समय") एल्गोरिदम लेता है। "

    एन → (2 एन) = 2 ( एन )

  • ... मैं एक ओ (एन²) ("वर्गबद्ध समय") एल्गोरिदम लेता है, तो डबल-स्क्वायर (चौगुनी)। " (उदाहरण के लिए 100x जितना बड़ा समस्या 100 वर्ग = 10000x जितनी देर तक लेती है ... संभवतः अस्थिर)

    एन² → (2 एन) ² = 4 ( एन² )

  • ... मैं डबल-क्यूबड (ऑक्टोपल) समय ओ (एन³) ("क्यूबिक टाइम") एल्गोरिदम लेता है। " (उदाहरण के लिए एक समस्या 100x जितनी बड़ी होती है 100³ = 1000000x लंबे समय तक ... बहुत ही असुरक्षित)

    सीएन³ → सी (2 एन) ³ = 8 ( सीएन³ )

  • ... मैं ओ (लॉग (एन)) ("लॉगरिदमिक टाइम") एल्गोरिदम लेता समय के लिए एक निश्चित राशि जोड़ता हूं। " (सस्ता!)

    सी लॉग (एन) → सी लॉग (2 एन) = (सी लॉग (2)) + ( सी लॉग (एन) ) = (निश्चित राशि) + ( सी लॉग (एन) )

  • ... मैं ओ (1) ("निरंतर समय") एल्गोरिदम लेता समय नहीं बदलता। " (सबसे सस्ता!)

    सी * 1सी * 1

  • ... मैं "(मूल रूप से) डबल" समय ओ (एन लॉग (एन)) एल्गोरिदम लेता है। " (काफी आम)

    यह ओ (एन 1.000001 ) से कम है, जिसे आप मूल रूप से रैखिक कॉल करने के इच्छुक हो सकते हैं

  • ... मैं हास्यास्पद रूप से एक ओ (2 एन ) ("घातीय समय") एल्गोरिदम लेता है। " (आप केवल एक इकाई द्वारा समस्या को बढ़ाकर डबल (या ट्रिपल, आदि) को दोगुना करेंगे)

    2 एन → 2 2 एन = (4 एन ) ............ एक और रास्ता डालें ...... 2 एन → 2 एन + 1 = 2 एन 2 1 = 2 2 एन

[गणितीय रूप से झुकाव के लिए, आप नाबालिग sidenotes के लिए spoilers पर माउस कर सकते हैं]

( https://.com/a/487292/711085 क्रेडिट के साथ)

(तकनीकी रूप से निरंतर कारक शायद कुछ और गूढ़ उदाहरणों में महत्वपूर्ण हो सकता है, लेकिन मैंने ऊपर की चीजों को phrased किया है (उदाहरण के लिए लॉग (एन) में) जैसे कि यह नहीं करता है)

ये विकास के रोटी और मक्खन आदेश हैं जो प्रोग्रामर और लागू कंप्यूटर वैज्ञानिक संदर्भ बिंदु के रूप में उपयोग करते हैं। वे इन्हें हर समय देखते हैं। (इसलिए जब आप तकनीकी रूप से सोच सकते हैं "इनपुट को दोगुना करने से ओ (√N) एल्गोरिदम 1.414 गुना धीमा हो जाता है," इसके बारे में सोचना बेहतर होता है "यह लॉगरिदमिक से भी बदतर है लेकिन रैखिक से बेहतर है।")

लगातार कारक

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

कुछ asymptotically बेहतर एल्गोरिदम (उदाहरण के लिए एक गैर तुलना O(N log(log(N))) सॉर्ट) इतनी बड़ी स्थिर कारक हो सकता है (उदाहरण के लिए 100000*N log(log(N)) ), या ओवरहेड जो अपेक्षाकृत बड़ा है जैसे O(N log(log(N))) एक छिपे + 100*N , कि वे "बड़े डेटा" पर भी उपयोग करने के लिए शायद ही कभी लायक हैं।

ओ (एन) कभी-कभी सबसे अच्छा क्यों कर सकता है, यानी हमें डेटास्ट्रक्चर की आवश्यकता क्यों है

O(N) एल्गोरिदम कुछ अर्थों में "सर्वोत्तम" एल्गोरिदम हैं यदि आपको अपने सभी डेटा को पढ़ने की आवश्यकता है। डेटा का एक गुच्छा पढ़ने का बहुत ही कार्य एक O(N) ऑपरेशन है। इसे स्मृति में लोड करना आम तौर पर O(N) (या यदि आपके पास हार्डवेयर समर्थन है, या यदि आप पहले ही डेटा पढ़ चुके हैं तो कोई भी समय नहीं है)। हालांकि यदि आप डेटा के हर टुकड़े को स्पर्श करते हैं या यहां तक ​​कि डेटा के हर दूसरे हिस्से को भी देखते हैं, तो आपका एल्गोरिदम इस दिखने के लिए O(N) समय लेगा। आपका वास्तविक एल्गोरिदम कितना समय लेता है, यह कम से कम O(N) क्योंकि उस समय उसने सभी डेटा को देखा था।

लेखन के बहुत ही कार्य के लिए भी यही कहा जा सकता है। सभी एल्गोरिदम जो एन चीजों को प्रिंट करते हैं, उन्हें एन समय लगेगा, क्योंकि उत्पादन कम से कम इतना लंबा होता है (उदाहरण के लिए सभी क्रमपरिवर्तन (पुनर्व्यवस्थित करने के तरीके) को प्रिंट करना एन प्लेइंग कार्ड का एक सेट फैक्टरियल है: O(N!) )।

यह डेटा संरचनाओं के उपयोग को प्रेरित करता है: डेटा संरचना को केवल एक बार डेटा (आमतौर पर O(N) समय) पढ़ने की आवश्यकता होती है, साथ ही कुछ मनमानी प्रीप्रोकैसिंग (जैसे O(N) या O(N log(N)) या O(N²) ) जिसे हम छोटे रखने की कोशिश करते हैं। उसके बाद, डेटा संरचना (सम्मिलन / विलोपन / इत्यादि) को संशोधित करना और डेटा पर प्रश्न बनाने में बहुत कम समय लगता है, जैसे O(1) या O(log(N)) । फिर आप बड़ी संख्या में प्रश्न पूछने के लिए आगे बढ़ते हैं! आम तौर पर, जितना अधिक काम आप समय से पहले करना चाहते हैं, उतना ही कम काम आपको बाद में करना होगा।

उदाहरण के लिए, कहें कि आपके पास लाखों सड़कों के खंडों का अक्षांश और देशांतर निर्देशांक था, और सभी सड़क चौराहे ढूंढना चाहता था।

  • बेवकूफ विधि: यदि आपके पास सड़क चौराहे के निर्देशांक थे, और आस-पास की सड़कों की जांच करना चाहते थे, तो आपको हर बार लाखों सेगमेंटों में जाना होगा, और प्रत्येक को आसन्नता के लिए जांचना होगा।
  • यदि आपको केवल एक बार ऐसा करने की आवश्यकता है, तो केवल एक बार O(N) काम की बेवकूफ विधि को करने में कोई समस्या नहीं होगी, लेकिन यदि आप इसे कई बार करना चाहते हैं (इस मामले में, N बार, एक बार प्रत्येक खंड), हमें O(N²) काम करना होगा, या 1000000 वर्ग = 1000000000000 संचालन करना होगा। अच्छा नहीं है (एक आधुनिक कंप्यूटर प्रति सेकंड एक अरब ऑपरेशन कर सकता है)।
  • यदि हम एक हैश टेबल (एक इंस्टेंट-स्पीड लुकअप टेबल, जिसे हैशैप या डिक्शनरी के नाम से भी जाना जाता है) नामक एक साधारण संरचना का उपयोग करते हैं, तो हम O(N) समय में सब कुछ प्रीप्रोसेसिंग करके एक छोटी सी लागत का भुगतान करते हैं। उसके बाद, यह केवल अपनी कुंजी से कुछ देखने के लिए औसत पर स्थिर समय लेता है (इस मामले में, हमारी कुंजी अक्षांश और देशांतर निर्देशांक है, जो ग्रिड में घिरा हुआ है; हम आसन्न ग्रिडस्पेस की खोज करते हैं जिनमें से केवल 9 हैं, जो कि केवल 9 हैं स्थिर)।
  • हमारा कार्य एक अक्षम O(N²) से एक प्रबंधनीय O(N) , और हमें बस इतना करना था कि हैश टेबल बनाने के लिए मामूली लागत का भुगतान किया गया हो।
  • समानता : इस विशेष मामले में समानता एक जिग्स पहेली है: हमने डेटा संरचना बनाई है जो डेटा की कुछ संपत्ति का शोषण करती है। यदि हमारे सड़क खंड पहेली टुकड़ों की तरह हैं, तो हम उन्हें रंग और पैटर्न से मेल करके समूहित करते हैं। इसके बाद हम बाद में अतिरिक्त काम करने से बचने के लिए इसका फायदा उठाते हैं (एक दूसरे के समान रंग के पहेली टुकड़ों की तुलना, हर दूसरे एकल पहेली टुकड़े के लिए नहीं)।

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

व्यावहारिक उदाहरण: कोडिंग के दौरान विकास के आदेशों को देखना

Asymptotic नोटेशन, इसके मूल पर, प्रोग्रामिंग से काफी अलग है। Asymptotic नोटेशन एक गणितीय ढांचे है कि चीजों के पैमाने के बारे में सोचने के लिए, और कई अलग-अलग क्षेत्रों में इस्तेमाल किया जा सकता है। उस ने कहा ... इस तरह आप कोडिंग के लिए एसिम्प्टोटिक नोटेशन लागू करते हैं।

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

(यहां, x एस कार्य, प्रोसेसर निर्देश, दुभाषिया opcodes, जो कुछ भी निरंतर समय इकाइयों का प्रतिनिधित्व करते हैं)

for(i=0; i<A; i++)        // A x ...
    some O(1) operation     // 1

--> A*1 --> O(A) time

visualization:

|<------ A ------->|
1 2 3 4 5 x x ... x

other languages, multiplying orders of growth:
  javascript, O(A) time and space
    someListOfSizeA.map((x,i) => [x,i])               
  python, O(rows*cols) time and space
    [[r*c for c in range(cols)] for r in range(rows)]

उदाहरण 2:

for every x in listOfSizeA:   // A x ...
    some O(1) operation         // 1
    some O(B) operation         // B
    for every y in listOfSizeC: // C x ...
        some O(1) operation       // 1

--> O(A*(1 + B + C))
    O(A*(B+C))        (1 is dwarfed)

visualization:

|<------ A ------->|
1 x x x x x x ... x

2 x x x x x x ... x ^
3 x x x x x x ... x |
4 x x x x x x ... x |
5 x x x x x x ... x B  <-- A*B
x x x x x x x ... x |
................... |
x x x x x x x ... x v

x x x x x x x ... x ^
x x x x x x x ... x |
x x x x x x x ... x |
x x x x x x x ... x C  <-- A*C
x x x x x x x ... x |
................... |
x x x x x x x ... x v

उदाहरण 3:

function nSquaredFunction(n) {
    total = 0
    for i in 1..n:        // N x
        for j in 1..n:      // N x
            total += i*k      // 1
    return total
}
// O(n^2)

function nCubedFunction(a) {
    for i in 1..n:                // A x
        print(nSquaredFunction(a))  // A^2
}
// O(a^3)

अगर हम थोड़ा जटिल करते हैं, तो भी आप कल्पना कर सकते हैं कि क्या हो रहा है:

for x in range(A):
    for y in range(1..x):
        simpleOperation(x*y)

x x x x x x x x x x |
x x x x x x x x x   |
x x x x x x x x     |
x x x x x x x       |
x x x x x x         |
x x x x x           |
x x x x             |
x x x               |
x x                 |
x___________________|

यहां, सबसे छोटी पहचान योग्य रूपरेखा जिसे आप आकर्षित कर सकते हैं वह महत्वपूर्ण है; एक त्रिकोण एक दो आयामी आकार (0.5 ए ^ 2) है, बस एक वर्ग की तरह एक द्वि-आयामी आकार (ए ^ 2) है; यहां दो का निरंतर कारक दोनों के बीच एसिम्प्टोटिक अनुपात में बनी हुई है, हालांकि हम इसे सभी कारकों की तरह अनदेखा करते हैं ... (इस तकनीक के लिए कुछ दुर्भाग्यपूर्ण बारीकियां हैं, मैं यहां नहीं जाता हूं; यह आपको गुमराह कर सकता है।)

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

यहां एक और चीज है जिसे हम दृष्टि से पहचान सकते हैं:

<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x
x x x x x x x x
x x x x
x x
x

हम इसे फिर से व्यवस्थित कर सकते हैं और इसे ओ (एन) देख सकते हैं:

<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x|x x x x x x x x|x x x x|x x|x

या हो सकता है कि आप ओ (एन * लॉग (एन)) कुल समय के लिए डेटा के लॉग (एन) पास करते हैं:

   <----------------------------- N ----------------------------->
 ^  x x x x x x x x x x x x x x x x|x x x x x x x x x x x x x x x x
 |  x x x x x x x x|x x x x x x x x|x x x x x x x x|x x x x x x x x
lgN x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x
 |  x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x
 v  x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x

असंबंधित रूप से लेकिन फिर से उल्लेख करने लायक है: यदि हम एक हैश (उदाहरण के लिए एक शब्दकोश / हैशटेबल लुकअप) करते हैं, तो यह ओ (1) का कारक है। यह बहुत तेज़ है।

[myDictionary.has(x) for x in listOfSizeA]
 \----- O(1) ------/    

--> A*1 --> O(A)

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

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

अमूर्त और औसत मामले जटिलता

"अमूर्त" और / या "औसत मामला" की अवधारणा भी है (ध्यान दें कि ये अलग हैं)।

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

अमूर्त सबसे खराब मामला : कुछ डेटा संरचनाओं में सबसे बुरी स्थिति जटिलता हो सकती है जो बड़ी है, लेकिन गारंटी है कि यदि आप इनमें से कई परिचालन करते हैं, तो आपके द्वारा किए गए काम की औसत मात्रा सबसे खराब स्थिति से बेहतर होगी। उदाहरण के लिए आपके पास एक डेटा संरचना हो सकती है जो आमतौर पर स्थिर O(1)समय लेती है । हालांकि, कभी-कभी यह 'हिचकी' करेगा और O(N)एक यादृच्छिक संचालन के लिए समय लेगा , क्योंकि शायद इसे कुछ बहीखाता या कचरा संग्रह या कुछ करने की ज़रूरत है ... लेकिन यह आपको वादा करता है कि अगर यह हिचकी करता है, तो यह एन के लिए फिर से हिचकी नहीं करेगा अधिक संचालन बुरी से बुरी हालत लागत अभी भी है O(N)आपरेशन प्रति, लेकिन परिशोधित लागत कई से ज्यादा रन है O(N)/N=O(1)प्रति ऑपरेशन। चूंकि बड़े परिचालन पर्याप्त दुर्लभ होते हैं, इसलिए कभी-कभी काम के बड़े पैमाने पर काम को लगातार कारक के रूप में मिश्रण करने के लिए माना जा सकता है। हम कहते हैं कि काम पर्याप्त रूप से बड़ी संख्या में कॉल पर "अमूर्त" है जो यह असम्बद्ध रूप से गायब हो जाता है।

अमूर्त विश्लेषण के लिए समानता:

आप एक कार चलाते हैं। कभी-कभी, आपको गैस स्टेशन पर जाने में 10 मिनट बिताने की ज़रूरत होती है और फिर गैस के साथ टैंक को भरने में 1 मिनट खर्च करते हैं। यदि आपने यह हर बार किया था जब भी आप अपनी कार के साथ कहीं भी गए थे (गैस स्टेशन पर ड्राइविंग करने में 10 मिनट खर्च करें, गैलन के एक अंश को भरने में कुछ सेकंड बिताएं), यह बहुत अक्षम होगा। लेकिन यदि आप हर कुछ दिनों में टैंक भरते हैं, तो गैस स्टेशन पर ड्राइविंग करने में 11 मिनट पर्याप्त संख्या में यात्राओं पर "अमूर्त" होते हैं, ताकि आप इसे अनदेखा कर सकें और अपने सभी यात्राओं का नाटक 5% अधिक हो।

औसत मामले और अमूर्त सबसे खराब मामले के बीच तुलना:

  • औसत मामला: हम अपने इनपुट के बारे में कुछ धारणाएं करते हैं; यानी यदि हमारे इनपुट की अलग-अलग संभावनाएं हैं, तो हमारे आउटपुट / रनटाइम्स में अलग-अलग संभावनाएं होंगी (जिन्हें हम औसत लेते हैं)। आम तौर पर हम मानते हैं कि हमारे इनपुट सभी समान रूप से (समान संभावना) हैं, लेकिन यदि असली दुनिया इनपुट "औसत इनपुट" की हमारी धारणाओं को फिट नहीं करते हैं, तो औसत आउटपुट / रनटाइम गणना अर्थहीन हो सकती है। यदि आप समान रूप से यादृच्छिक इनपुट की उम्मीद करते हैं, तो यह सोचने के लिए उपयोगी है!
  • अमूर्त सबसे खराब मामला: यदि आप एक अमूर्त सबसे खराब केस डेटा संरचना का उपयोग करते हैं, तो प्रदर्शन को आवंटित सबसे बुरी स्थिति के भीतर होने की गारंटी दी जाती है ... अंततः (यदि इनपुट एक दुष्ट राक्षस द्वारा चुने जाते हैं जो सबकुछ जानता है और कोशिश कर रहा है आपको पेंच)। आम तौर पर हम इसका उपयोग एल्गोरिदम का विश्लेषण करने के लिए करते हैं जो अप्रत्याशित बड़े हिचकी के साथ प्रदर्शन में बहुत 'चंचल' हो सकता है, लेकिन समय के साथ-साथ अन्य एल्गोरिदम भी प्रदर्शन करता है। (हालांकि, जब तक आपकी डेटा संरचना में बहुत ही उत्कृष्ट काम के लिए ऊपरी सीमा नहीं है, तो यह विलंब करने के लिए तैयार है, एक बुरा हमलावर शायद आपको एक बार में अधिकतम विलंबित कार्य को पकड़ने के लिए मजबूर कर सकता है।

हालांकि, अगर आप किसी हमलावर के बारे में चिंतित हैं, तो अमूर्तकरण और औसत मामले के अलावा चिंता करने के लिए कई अन्य एल्गोरिदमिक हमले वैक्टर हैं।)

औसत मामले और परिशोधन दोनों दिमाग में स्केलिंग के बारे में सोचने और डिजाइन करने के लिए अविश्वसनीय रूप से उपयोगी उपकरण हैं।

( यदि इस उप-विषयक पर रूचि है तो औसत मामले और अमूर्त विश्लेषण के बीच अंतर देखें ।)

बहुआयामी बड़े-ओ

ज्यादातर समय, लोगों को यह एहसास नहीं होता कि काम पर एक से अधिक परिवर्तनीय हैं। उदाहरण के लिए, एक स्ट्रिंग-सर्च एल्गोरिदम में, आपके एल्गोरिदम में समय लग सकता है O([length of text] + [length of query]), यानी यह दो चरों में रैखिक है O(N+M)। अन्य बेवकूफ एल्गोरिदम हो सकते हैं O([length of text]*[length of query])या O(N*M)। एकाधिक चरों को अनदेखा करना एल्गोरिदम विश्लेषण में देखे जाने वाले सबसे आम निरीक्षणों में से एक है, और एल्गोरिदम को डिज़ाइन करते समय आपको विकलांग बना सकता है।

पूरी कहानी

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

यह भी ध्यान रखें कि आपके कार्यक्रम की छिपी बाधाओं के कारण, आप वास्तव में एसिम्प्टोटिक व्यवहार की परवाह नहीं कर सकते हैं। आप मूल्यों की एक सीमित संख्या के साथ काम कर रहे हैं, उदाहरण के लिए:

  • यदि आप 5 तत्वों की तरह कुछ सॉर्ट कर रहे हैं, तो आप तेज़ O(N log(N))क्विकॉर्ट का उपयोग नहीं करना चाहते हैं ; आप प्रविष्टि प्रकार का उपयोग करना चाहते हैं, जो छोटे इनपुट पर अच्छा प्रदर्शन करने के लिए होता है। ये परिस्थितियां अक्सर विभाजित और एल्गोरिदम को जीतने में आती हैं, जहां आप समस्या को छोटे और छोटे उपप्रोबल में विभाजित करते हैं, जैसे रिकर्सिव सॉर्टिंग, फास्ट फूरियर ट्रांसफॉर्म, या मैट्रिक्स गुणा।
  • अगर कुछ मूल्यों को कुछ छुपे हुए तथ्यों के कारण प्रभावी रूप से बाध्य किया जाता है (उदाहरण के लिए औसत मानव नाम शायद 40 अक्षरों पर धीरे-धीरे बंधे होते हैं, और मानव युग लगभग 150 पर धीरे-धीरे बंधे होते हैं)। शब्दों को निरंतर प्रभावी बनाने के लिए आप अपने इनपुट पर सीमाएं लगा सकते हैं।

व्यावहारिक रूप से, एल्गोरिदम के बीच भी, जिसमें समान या समान एसिम्प्टोटिक प्रदर्शन होता है, उनकी सापेक्ष योग्यता वास्तव में अन्य चीजों द्वारा संचालित की जा सकती है, जैसे कि: अन्य प्रदर्शन कारक (क्विकॉर्ट और विलय दोनों ही हैं O(N log(N)), लेकिन क्विकॉर्टोर्ट सीपीयू कैश का लाभ लेता है); कार्यान्वयन की आसानी जैसे गैर-प्रदर्शन विचार; चाहे पुस्तकालय उपलब्ध है, और लाइब्रेरी कितनी प्रतिष्ठित और रखरखाव है।

कार्यक्रम 500 मेगाहट्र्ज कंप्यूटर बनाम 2GHz कंप्यूटर पर भी धीमी गति से चलेंगे। हम वास्तव में संसाधन सीमाओं के हिस्से के रूप में नहीं मानते हैं, क्योंकि हम मशीन संसाधनों (उदाहरण के लिए प्रति घड़ी चक्र) के मामले में स्केलिंग के बारे में सोचते हैं, प्रति वास्तविक दूसरे नहीं। हालांकि, ऐसी ही चीजें हैं जो 'गुप्त रूप से' प्रदर्शन को प्रभावित कर सकती हैं, जैसे कि आप अनुकरण के तहत चल रहे हैं या फिर संकलक अनुकूलित कोड या नहीं। ये कुछ बुनियादी परिचालनों को लंबे समय तक ले सकते हैं (यहां तक ​​कि एक-दूसरे के सापेक्ष भी), या कुछ ऑपरेशन को गतिमान रूप से गति या धीमा कर सकते हैं (एक-दूसरे के सापेक्ष भी)। प्रभाव विभिन्न कार्यान्वयन और / या पर्यावरण के बीच छोटा या बड़ा हो सकता है। क्या आप उस छोटे अतिरिक्त काम को बाहर निकालने के लिए भाषा या मशीनों को स्विच करते हैं? यह सौ अन्य कारणों (आवश्यकता, कौशल, सहकर्मी, प्रोग्रामर उत्पादकता,आपके समय, परिचितता, कामकाज का मौद्रिक मूल्य, विधानसभा या जीपीयू क्यों नहीं ...), जो प्रदर्शन से अधिक महत्वपूर्ण हो सकता है।

उपर्युक्त मुद्दों, जैसे प्रोग्रामिंग भाषा, लगभग स्थिर कारक के हिस्से के रूप में कभी नहीं माना जाता है (न ही वे होना चाहिए); फिर भी उनमें से किसी को अवगत होना चाहिए, क्योंकि कभी-कभी (हालांकि शायद ही कभी) वे चीजों को प्रभावित कर सकते हैं। उदाहरण के लिए, cpython में, मूल प्राथमिकता कतार कार्यान्वयन असम्बद्ध रूप से गैर-इष्टतम है ( सम्मिलन या खोज-मिनट की आपकी पसंद के O(log(N))बजाय O(1)); क्या आप एक और कार्यान्वयन का उपयोग करते हैं? शायद नहीं, चूंकि सी कार्यान्वयन संभवतः तेज़ है, और शायद अन्य समान समस्याएं कहीं और हैं। ट्रेडऑफ हैं; कभी-कभी वे मायने रखते हैं और कभी-कभी वे नहीं करते हैं।

( संपादित करें : "सादा अंग्रेजी" स्पष्टीकरण यहां समाप्त होता है।)

गणित addenda

पूर्णता के लिए, बड़े-ओ नोटेशन की सटीक परिभाषा निम्नानुसार है: f(x) ∈ O(g(x))इसका अर्थ यह है कि "एफ असम्बद्ध रूप से कॉन्स्ट * जी द्वारा ऊपरी-बाध्य है": एक्स के कुछ सीमित मूल्य से नीचे सब कुछ अनदेखा कर रहा है, ऐसे में स्थिरता मौजूद है |f(x)| ≤ const * |g(x)|। (अन्य प्रतीकों निम्नानुसार हैं: Oअर्थों की तरह ≤, Ωमतलब ≥। लोअरकेस वेरिएंट हैं: oमतलब <, और ωसाधन>।) का f(x) ∈ Ɵ(g(x))अर्थ है f(x) ∈ O(g(x))और f(x) ∈ Ω(g(x))(ऊपरी- और जी द्वारा निचला बाध्य): कुछ स्थिरांक मौजूद हैं जैसे कि f हमेशा "बैंड" के बीच में झूठ होगा const1*g(x)और const2*g(x)। यह सबसे मजबूत एसिम्प्टोटिक स्टेटमेंट है जिसे आप बना सकते हैं और मोटे तौर पर बराबर कर सकते हैं==। (क्षमा करें, मैंने स्पष्टता के लिए अब तक पूर्ण मूल्य प्रतीकों के उल्लेख में देरी करने के लिए निर्वाचित किया है, विशेष रूप से क्योंकि मैंने कभी भी नकारात्मक विज्ञान मूल्यों को कंप्यूटर विज्ञान संदर्भ में नहीं देखा है।)

लोग अक्सर उपयोग करेंगे = O(...), जो शायद अधिक सही 'कंप-विज्ञान' नोटेशन है, और पूरी तरह से उपयोग करने के लिए वैध है ... लेकिन किसी को यह समझना चाहिए कि =समानता के रूप में उपयोग नहीं किया जा रहा है; यह एक यौगिक नोटेशन है जिसे एक मुहावरे के रूप में पढ़ा जाना चाहिए। मुझे और अधिक कठोर उपयोग करने के लिए सिखाया गया था ∈ O(...)मतलब "का एक तत्व है"। O(N²)वास्तव में एक समानता वर्ग है , यानी, यह उन चीजों का एक सेट है जिसे हम समान मानते हैं। इस विशेष मामले में, O(N²)जैसे {तत्व शामिल हैं 2 N², 3 N², 1/2 N², 2 N² + log(N), - N² + N^1.9, ...} और असीम बड़ी है, लेकिन यह अभी भी एक सेट है।=नोटेशन अधिक आम हो सकता है, और यहां तक ​​कि विश्व प्रसिद्ध कंप्यूटर वैज्ञानिकों द्वारा कागजात में भी प्रयोग किया जाता है। इसके अतिरिक्त, अक्सर यह मामला होता है कि एक आरामदायक सेटिंग में, लोग कहेंगे O(...)जब उनका मतलब होगा Ɵ(...); यह तकनीकी रूप से सच है क्योंकि चीजों Ɵ(exactlyThis)का सेट एक सबसेट है O(noGreaterThanThis)... और टाइप करना आसान है। ;-)


बिग ओ एक फ़ंक्शन के विकास व्यवहार पर ऊपरी सीमा का वर्णन करता है, उदाहरण के लिए एक प्रोग्राम का रनटाइम, जब इनपुट बड़ा हो जाता है।

उदाहरण:

  • ओ (एन): अगर मैं इनपुट आकार को रनटाइम डबल्स दोगुना करता हूं

  • ओ (एन 2 ): यदि इनपुट आकार रनटाइम चौगुनी को दोगुना करता है

  • ओ (लॉग एन): यदि इनपुट आकार एक बार रनटाइम बढ़ता है

  • ओ (2 एन ): यदि इनपुट आकार एक से बढ़ता है, रनटाइम युगल

इनपुट आकार आमतौर पर इनपुट का प्रतिनिधित्व करने के लिए आवश्यक बिट्स में स्थान होता है।


यह दिखाता है कि कैसे एक एल्गोरिदम स्केल करता है।

ओ (एन 2 ) : क्वाड्रैटिक जटिलता के रूप में जाना जाता है

  • 1 आइटम: 1 सेकंड
  • 10 आइटम: 100 सेकंड
  • 100 आइटम: 10000 सेकेंड

ध्यान दें कि वस्तुओं की संख्या 10 के कारक से बढ़ जाती है, लेकिन समय 10 के कारक से बढ़ता है। असल में, एन = 10 और इसलिए ओ (एन 2 ) हमें स्केलिंग कारक एन 2 देता है जो 10 2 है

ओ (एन) : रैखिक जटिलता के रूप में जाना जाता है

  • 1 आइटम: 1 सेकंड
  • 10 आइटम: 10 सेकंड
  • 100 आइटम: 100 सेकंड

इस बार वस्तुओं की संख्या 10 के कारक से बढ़ जाती है, और ऐसा समय भी होता है। एन = 10 और इसलिए ओ (एन) स्केलिंग कारक 10 है।

ओ (1) : निरंतर जटिलता के रूप में जाना जाता है

  • 1 आइटम: 1 सेकंड
  • 10 आइटम: 1 सेकंड
  • 100 आइटम: 1 सेकंड

वस्तुओं की संख्या अभी भी 10 के कारक से बढ़ रही है, लेकिन ओ (1) के स्केलिंग कारक हमेशा 1 है।

ओ (लॉग एन) : लॉगरिदमिक जटिलता के रूप में जाना जाता है

  • 1 आइटम: 1 सेकंड
  • 10 आइटम: 2 सेकंड
  • 100 आइटम: 3 सेकंड
  • 1000 आइटम: 4 सेकंड
  • 10000 आइटम: 5 सेकंड

गणना की संख्या केवल इनपुट मान के लॉग द्वारा बढ़ी है। तो इस मामले में, मानते हैं कि प्रत्येक गणना में 1 सेकंड लगते हैं, इनपुट n का log n आवश्यक समय है, इसलिए log n

यह इसका सारांश है। वे गणित को कम करते हैं, इसलिए यह वास्तव में एन 2 नहीं हो सकता है या जो भी वे कहते हैं, लेकिन यह स्केलिंग में हावी कारक होगा।


आप बड़े ओ के बारे में जानना चाहते हैं? मैं भी ऐसा करूँ।

तो बड़े ओ के बारे में बात करने के लिए, मैं उन शब्दों का उपयोग करूंगा जिनके पास सिर्फ एक हरा है। प्रति शब्द एक ध्वनि। छोटे शब्द जल्दी हैं। आप इन शब्दों को जानते हैं, और ऐसा करते हैं। हम शब्दों को एक ध्वनि के साथ प्रयोग करेंगे। वे छोटे हैं। मुझे यकीन है कि आप उन सभी शब्दों को जानेंगे जिनका हम उपयोग करेंगे!

अब, आप और मैं काम की बात करते हैं। ज्यादातर समय, मुझे काम पसंद नहीं है। क्या आपको काम पसंद है? यह मामला हो सकता है जो आप करते हैं, लेकिन मुझे यकीन है कि मैं नहीं करता हूं।

मुझे काम पर जाना पसंद नहीं है। मुझे काम पर समय बिताना पसंद नहीं है। अगर मेरे पास रास्ता था, तो मैं सिर्फ खेलना चाहता हूं, और मजेदार चीजें करता हूं। क्या आप वही महसूस करते हैं जैसा मैं करता हूं?

अब कभी-कभी मुझे काम पर जाना पड़ता है। यह दुख की बात है लेकिन सच है। इसलिए, जब मैं काम पर हूं, मेरे पास एक नियम है: मैं कम काम करने की कोशिश करता हूं। जैसा कि मैं कर सकता हूं के रूप में कोई काम नहीं है। तब मैं खेलता हूँ!

तो यहां बड़ी खबर है: बड़ा ओ मुझे काम नहीं करने में मदद कर सकता है! मैं अधिक समय खेल सकता हूं, अगर मुझे बड़ा पता है। कम काम, और खेलें! यही वह बड़ा है जो मुझे करने में मदद करता है।

अब मेरे पास कुछ काम है। मेरे पास यह सूची है: एक, दो, तीन, चार, पांच, छः। मुझे इस सूची में सभी चीजें जोड़नी होंगी।

वाह, मुझे काम से नफरत है। लेकिन ओह ठीक है, मुझे यह करना है। तो मैं यहाँ जाता हूँ।

एक प्लस दो तीन है ... प्लस तीन छः है ... और चार है ... मुझे नहीं पता। मैं खो गया। मेरे सिर में करना मेरे लिए बहुत मुश्किल है। मुझे इस तरह के काम की ज्यादा परवाह नहीं है।

तो चलो काम नहीं करते हैं। चलो आप और मैं बस सोचते हैं कि यह कितना मुश्किल है। छः संख्याओं को जोड़ने के लिए मुझे कितना काम करना होगा?

अच्छा चलो देखते हैं। मुझे एक और दो जोड़ना होगा, और उसके बाद इसे तीन में जोड़ना होगा, और उसके बाद इसे चार में जोड़ दें ... बिलकुल भी, मैं छह जोड़ों को गिनता हूं। मुझे इसे हल करने के लिए छह जोड़ना है।

यहां हमें यह बताने के लिए बड़ा ओ आता है कि यह गणित कितना मुश्किल है।

बिग ओ कहते हैं: इसे हल करने के लिए हमें छह जोड़ना होगा। एक जोड़, प्रत्येक चीज़ के लिए एक से छः तक। काम के छह छोटे बिट्स ... काम का प्रत्येक बिट एक जोड़ है।

खैर, मैं अब उन्हें जोड़ने के लिए काम नहीं करूंगा। लेकिन मुझे पता है कि यह कितना मुश्किल होगा। यह छह जोड़ों होगा।

अरे नहीं, अब मेरे पास और काम है। शीश। इस तरह की चीजें कौन बनाता है ?!

अब वे मुझसे एक से दस में जोड़ने के लिए कहते हैं! मैं ऐसा क्यों करूंगा? मैं एक से छः जोड़ना नहीं चाहता था। एक से दस में जोड़ने के लिए ... अच्छा ... यह और भी कठिन होगा!

यह कितना मुश्किल होगा? मुझे और कितना काम करना होगा? क्या मुझे कम या ज्यादा कदम चाहिए?

खैर, मुझे लगता है कि मुझे दस जोड़ना होगा ... प्रत्येक चीज़ के लिए एक से दस तक। दस छह से अधिक है। मुझे एक से दस तक, एक से छह तक जोड़ने के लिए और भी बहुत कुछ करना होगा!

मैं अभी जोड़ना नहीं चाहता हूं। मैं बस इतना सोचना चाहता हूं कि इसमें कितना मुश्किल हो सकता है। और, मुझे आशा है कि जितनी जल्दी हो सके खेलें।

एक से छः तक जोड़ने के लिए, यह कुछ काम है। लेकिन क्या आप देखते हैं, एक से दस में जोड़ने के लिए, यह अधिक काम है?

बिग ओ आपका दोस्त और मेरा है। बिग ओ हमें यह सोचने में मदद करता है कि हमें कितना काम करना है, इसलिए हम योजना बना सकते हैं। और, अगर हम बड़े ओ के साथ दोस्त हैं, तो वह हमें ऐसे काम को चुनने में मदद कर सकता है जो इतना कठिन नहीं है!

अब हमें नया काम करना होगा। अरे नहीं। मुझे यह काम बिल्कुल पसंद नहीं है।

नया काम है: सभी चीजों को एक से एन में जोड़ें।

रुकिए! एन क्या है क्या मुझे याद आया? यदि आप मुझे नहीं बताते कि मैं क्या एन हूं तो मैं एक से एन में कैसे जोड़ सकता हूं?

खैर, मुझे नहीं पता कि एन क्या है। मुझे नहीं बताया गया था। क्या तुम? नहीं? ओह अच्छा। तो हम काम नहीं कर सकते हैं। वाह।

लेकिन हालांकि हम अब काम नहीं करेंगे, हम अनुमान लगा सकते हैं कि यह कितना मुश्किल होगा, अगर हम जानते थे। हमें एन चीजों को जोड़ना होगा, है ना? बेशक!

अब यहां बड़ा ओ आता है, और वह हमें बताएगा कि यह काम कितना मुश्किल है। वह कहता है: सभी चीजों को एक से एन में जोड़ने के लिए, एक-एक करके, ओ (एन) है। इन सभी चीजों को जोड़ने के लिए, [मुझे पता है कि मुझे एन बार जोड़ना होगा।] [1] यह बड़ा है ओ! वह हमें बताता है कि कुछ प्रकार के काम करना कितना मुश्किल है।

मेरे लिए, मैं बड़े ओ के बारे में सोचता हूं जैसे एक बड़ा, धीमा, मालिक आदमी। वह काम पर सोचता है, लेकिन वह ऐसा नहीं करता है। वह कह सकता है, "वह काम जल्दी है।" या, वह कह सकता है, "वह काम इतना धीमा और कठिन है!" लेकिन वह काम नहीं करता है। वह सिर्फ काम को देखता है, और फिर वह हमें बताता है कि यह कितना समय ले सकता है।

मुझे बड़ी ओ के लिए बहुत परवाह है। क्यों? मुझे काम करना अच्छा नहीं लगता! कोई भी काम करना पसंद नहीं करता है। यही कारण है कि हम सभी बड़े ओ प्यार करते हैं! वह हमें बताता है कि हम कितनी तेजी से काम कर सकते हैं। वह हमें यह सोचने में मदद करता है कि कितना कड़ी मेहनत है।

ओह ओह, अधिक काम। अब, काम नहीं करते हैं। लेकिन, चलो कदम, कदम से कदम करने की योजना बनाते हैं।

उन्होंने हमें दस कार्ड का डेक दिया। वे सब मिश्रित हैं: सात, चार, दो, छः ... बिल्कुल नहीं। और अब ... हमारा काम उन्हें सॉर्ट करना है।

Ergh। यह बहुत काम की तरह लगता है!

हम इस डेक को कैसे व्यवस्थित कर सकते हैं? मेरे पास एक योजना है।

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

जब डेक किया जाता है, तो मैं पूछता हूं: क्या मैंने उस पास कार्ड को स्वैप किया था? यदि ऐसा है, तो मुझे शीर्ष पर, इसे एक बार फिर से करना होगा।

किसी बिंदु पर, कुछ समय पर, कोई स्वैप नहीं होगा, और हमारे प्रकार का डेक किया जाएगा। इतना सारा कार्य!

खैर, उन नियमों के साथ कार्ड को सॉर्ट करने के लिए, कितना काम होगा?

मेरे पास दस कार्ड हैं और, ज्यादातर समय - यानी, अगर मेरे पास बहुत भाग्य नहीं है - मुझे डेक के माध्यम से हर बार दस कार्ड स्वैप के साथ पूरे डेक तक दस गुना तक जाना होगा।

बिग हे, मेरी मदद करो!

बिग ओ आता है और कहता है: एन कार्ड के डेक के लिए, इसे सॉर्ट करने के लिए ओ (एन वर्ग) समय में किया जाएगा।

वह एन वर्ग क्यों कहता है?

खैर, आप जानते हैं कि एन वर्ग एन एन एन है। अब, मुझे यह मिल गया: एन कार्ड चेक किए गए, डेक के माध्यम से क्या हो सकता है। वह दो लूप है, प्रत्येक एन कदम के साथ। यह एन वर्ग इतना काम किया जाना है। निश्चित रूप से बहुत सारे काम!

अब जब बड़ा ओ कहता है कि यह ओ (एन वर्ग) काम करेगा, तो उसका मतलब नाक पर एन स्क्वायर जोड़ना नहीं है। कुछ मामलों के लिए यह कुछ छोटा हो सकता है। लेकिन सबसे बुरे मामले में, यह डेक को सॉर्ट करने के लिए काम के एन वर्ग चरणों के पास होगा।

अब यहां है जहां बड़ा ओ हमारा दोस्त है।

बिग ओ इस बात को इंगित करता है: जैसे एन बड़ा हो जाता है, जब हम कार्ड को सॉर्ट करते हैं, तो जॉब पुराने-इन-इन-चीज जॉब की तुलना में बहुत अधिक कठिन हो जाता है। हम इसके बारे में कैसे जानते हैं?

खैर, अगर एन वास्तविक हो जाता है, तो हमें परवाह नहीं है कि हम एन या एन वर्ग में क्या जोड़ सकते हैं।

बड़े एन के लिए, एन वर्ग एन से अधिक बड़ा है।

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

बिग ओ हमारे लिए काम हल नहीं करता है। बिग ओ हमें बताता है कि काम कितना मुश्किल है।

मेरे पास कार्ड का डेक है। मैंने उन्हें सॉर्ट किया। आपने मदद की। धन्यवाद।

कार्ड को सॉर्ट करने का कोई और तेज़ तरीका है? क्या बड़ा हे हमारी मदद कर सकता है?

हाँ, एक और तेज़ तरीका है! सीखने में कुछ समय लगता है, लेकिन यह काम करता है ... और यह काफी तेज़ काम करता है। आप इसे भी आजमा सकते हैं, लेकिन अपना समय प्रत्येक चरण के साथ लें और अपनी जगह न खोएं।

डेक को सॉर्ट करने के इस नए तरीके में, हम कुछ समय पहले कार्ड के जोड़े की जांच नहीं करते थे। इस डेक को सॉर्ट करने के लिए आपके नए नियम यहां दिए गए हैं:

एक: मैं डेक के हिस्से में एक कार्ड चुनता हूं जिसे हम अभी काम करते हैं। यदि आप चाहें तो आप मेरे लिए एक चुन सकते हैं। (पहली बार हम ऐसा करते हैं, "डेक का हिस्सा जो हम अभी काम करते हैं" बिल्कुल पूरा डेक है।)

दो: मैंने आपके द्वारा चुने गए कार्ड पर डेक चलाया। यह स्प्ले क्या है; मैं कैसे खेलूँ? खैर, मैं स्टार्ट कार्ड से एक-एक करके नीचे जाता हूं, और मैं ऐसे कार्ड की तलाश करता हूं जो स्प्ले कार्ड से अधिक है।

तीन: मैं एंड कार्ड से जाता हूं, और मैं ऐसे कार्ड की तलाश करता हूं जो स्प्ले कार्ड से अधिक कम है।

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

कुछ बिंदु पर, यह पाश (दो से तीन तक) समाप्त हो जाएगा। यह समाप्त होता है जब इस खोज के दोनों हिस्सों को स्प्ले कार्ड पर मिलते हैं। फिर, हमने आपके द्वारा चरण 1 में चुने गए कार्ड के साथ डेक को बस चलाया है। अब, शुरुआत के पास सभी कार्ड स्प्ले कार्ड से अधिक कम हैं; और अंत में कार्ड स्प्ले कार्ड से अधिक अधिक हैं। कूल चाल!

चार (और यह मजेदार हिस्सा है): मेरे पास दो छोटे डेक हैं, स्प्ले कार्ड से एक और कम, और एक और उच्च। अब मैं प्रत्येक छोटे डेक पर एक कदम पर जाता हूं! यही कहना है, मैं पहले छोटे डेक पर चरण वन से शुरू करता हूं, और जब यह काम पूरा हो जाता है, तो मैं अगले छोटे डेक पर चरण वन से शुरू होता हूं।

मैं भागों में डेक तोड़ता हूं, और प्रत्येक भाग को और अधिक छोटा और छोटा करता हूं, और कुछ समय में मेरे पास और काम करने का कोई काम नहीं होता है। अब यह सभी नियमों के साथ धीमा प्रतीत हो सकता है। लेकिन मेरा विश्वास करो, यह बिल्कुल धीमा नहीं है। चीजों को हल करने के पहले तरीके से यह बहुत कम काम है!

इस तरह का क्या कहा जाता है? इसे त्वरित क्रमबद्ध कहा जाता है! उस तरह का कार कार होयर नामक एक आदमी द्वारा बनाया गया था और उसने इसे त्वरित सॉर्ट कहा था। अब, त्वरित सॉर्ट हर समय उपयोग किया जाता है!

त्वरित सॉर्ट छोटे लोगों में बड़े डेक तोड़ देता है। यही कहना है, यह छोटे कार्यों में बड़े कार्यों को तोड़ देता है।

हममम। वहां एक नियम हो सकता है, मुझे लगता है। बड़े कार्यों को छोटा बनाने के लिए, उन्हें तोड़ दें।

यह तरह काफी जल्दी है। कितनी जल्दी बिग ओ हमें बताता है: इस मामले में ओ (एन लॉग एन) काम करने की जरूरत है, मतलब मामले में।

क्या यह पहले प्रकार की तुलना में कम या ज्यादा तेज़ है? बिग ओ, कृपया मदद करें!

पहला प्रकार ओ (एन वर्ग) था। लेकिन त्वरित क्रम ओ है (एन लॉग एन)। आप जानते हैं कि एन लॉग एन एन वर्ग से कम है, बड़े एन के लिए, है ना? खैर, इस तरह हम जानते हैं कि त्वरित क्रम तेजी से है!

यदि आपको डेक सॉर्ट करना है, तो सबसे अच्छा तरीका क्या है? खैर, आप जो भी चाहते हैं वह कर सकते हैं, लेकिन मैं त्वरित सॉर्ट का चयन करूंगा।

मैं त्वरित सॉर्ट क्यों चुनूं? मैं निश्चित रूप से काम करना पसंद नहीं करता! मैं काम पूरा करना चाहता हूं जैसे ही मैं इसे पूरा कर सकता हूं।

मुझे कैसे पता चलेगा कि त्वरित सॉर्ट कम काम है? मुझे पता है कि ओ (एन लॉग एन) ओ (एन वर्ग) से कम है। ओ अधिक छोटे हैं, इसलिए त्वरित क्रम कम काम है!

अब आप मेरे दोस्त, बिग ओ को जानते हैं। वह हमें कम काम करने में मदद करता है। और यदि आप बड़े ओ को जानते हैं, तो आप भी कम काम कर सकते हैं!

तुमने मेरे साथ सब कुछ सीखा! तुम बहुत ही स्मार्ट हो! आपको बहुत - बहुत धन्यवाद!

अब वह काम हो गया है, चलो चलें!

[1]: धोखा देने और सभी चीजों को एक से एक में जोड़ने के लिए एक तरीका है, सब एक बार में। गॉस नाम के कुछ बच्चे को यह पता चला कि वह आठ वर्ष का था। हालांकि मैं उस स्मार्ट नहीं हूं, इसलिए मुझसे मत पूछो कि उसने ऐसा कैसे किया


If you plot a logarithmic function on a graphical calculator or something similar, you'll see that it rises really slowly -- even more slowly than a linear function.

This is why algorithms with a logarithmic time complexity are highly sought after: even for really big n (let's say n = 10^8, for example), they perform more than acceptably.





algorithm complexity-theory computer-science big-o time-complexity