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




complexity-theory computer-science (20)

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

https://code.i-harness.com


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

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

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

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

    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 से अधिक नोटेशन हैं।

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

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

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

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

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


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

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

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

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

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

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

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


प्रस्तावना

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

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

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

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

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

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

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


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

बिग ओ जटिलता को इस ग्राफ के साथ देखा जा सकता है:

बिग-ओ नोटेशन के लिए मैं सबसे सरल परिभाषा दे सकता हूं:

बिग-ओ नोटेशन एल्गोरिदम की जटिलता का सापेक्ष प्रतिनिधित्व है।

उस वाक्य में कुछ महत्वपूर्ण और जानबूझकर चुने गए शब्द हैं:

  • सापेक्ष: आप सेब से सेब की तुलना कर सकते हैं। आप एल्गोरिदम की तुलना एल्गोरिदम के लिए गणित गुणा करने के लिए तुलना नहीं कर सकते हैं जो पूर्णांक की एक सूची टाइप करता है। लेकिन अंकगणितीय परिचालन करने के लिए दो एल्गोरिदम की तुलना (एक गुणा, एक जोड़ा) आपको कुछ सार्थक बताएगा;
  • प्रतिनिधित्व: बिग-ओ (अपने सबसे सरल रूप में) एल्गोरिदम के बीच एक एकल चर में तुलना को कम करता है। उस चर को अवलोकन या धारणाओं के आधार पर चुना जाता है। उदाहरण के लिए, सॉर्टिंग एल्गोरिदम आमतौर पर तुलना संचालन के आधार पर तुलना की जाती है (दो नोड्स की तुलना उनके सापेक्ष क्रम को निर्धारित करने के लिए)। यह मानता है कि तुलना महंगा है। लेकिन क्या होगा यदि तुलना सस्ता है लेकिन स्वैपिंग महंगा है? यह तुलना बदलता है; तथा
  • जटिलता: अगर 10,000 तत्वों को क्रमबद्ध करने में मुझे एक सेकंड लगता है तो मुझे दस लाख को क्रमबद्ध करने में कितना समय लगेगा? इस उदाहरण में जटिलता कुछ और के लिए एक सापेक्ष उपाय है।

वापस आओ और जब आप बाकी पढ़ लेंगे तो उपरोक्त को दोबारा पढ़ें।

बिग-ओ का सबसे अच्छा उदाहरण मैं सोच सकता हूं कि अंकगणित कर रहा है। दो नंबर लें (123456 और 78 9 012)। स्कूल में हमने जो मूल अंकगणितीय परिचालन सीखा था वे थे:

  • इसके अलावा,
  • घटाव;
  • गुणन; तथा
  • विभाजन।

इनमें से प्रत्येक एक ऑपरेशन या एक समस्या है। इन्हें हल करने की एक विधि को एल्गोरिदम कहा जाता है

जोड़ सबसे सरल है। आप संख्याओं को दाएं (दाईं ओर) पंक्तिबद्ध करते हैं और परिणामों में उस जोड़ की अंतिम संख्या लिखने वाले कॉलम में अंक जोड़ते हैं। उस संख्या का 'दसवां हिस्सा' अगले कॉलम पर ले जाया जाता है।

आइए मान लें कि इन संख्याओं को जोड़ने के लिए इस एल्गोरिदम में सबसे महंगा ऑपरेशन है। इसका कारण यह है कि इन दो संख्याओं को एक साथ जोड़ने के लिए हमें 6 अंकों को जोड़ना होगा (और संभवतः 7 वें स्थान पर)। यदि हम एक साथ दो 100 अंक संख्या जोड़ते हैं तो हमें 100 जोड़ों को करना होगा। यदि हम दो 10,000 अंकों की संख्या जोड़ते हैं तो हमें 10,000 जोड़ना होगा।

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

घटाव समान है (सिवाय इसके कि आपको ले जाने के बजाय उधार लेने की आवश्यकता हो सकती है)।

गुणा अलग है। आप संख्याओं को लाइन करते हैं, नीचे अंक में पहला अंक लें और प्रत्येक अंक के माध्यम से प्रत्येक अंक के मुकाबले इसे गुणा करें। तो हमारे दो 6 अंकों की संख्या गुणा करने के लिए हमें 36 गुणा करना होगा। अंतिम परिणाम प्राप्त करने के लिए हमें 10 या 11 कॉलम जोड़ना पड़ सकता है।

यदि हमारे पास दो 100 अंकों की संख्या है तो हमें 10,000 गुणा करने और 200 जोड़ों की आवश्यकता है। दो लाख अंकों की संख्या के लिए हमें एक ट्रिलियन (10 12 ) गुणा करने और दो मिलियन जोड़ों की आवश्यकता है।

एन- स्क्वायर के साथ एल्गोरिदम स्केल के रूप में, यह ओ (एन 2 ) या वर्गिक जटिलता है । यह एक और महत्वपूर्ण अवधारणा पेश करने का एक अच्छा समय है:

हम केवल जटिलता के सबसे महत्वपूर्ण हिस्से की परवाह करते हैं।

अस्थिर ने महसूस किया होगा कि हम संचालन की संख्या को व्यक्त कर सकते हैं: n 2 + 2n। लेकिन जैसा कि आपने हमारे उदाहरण से दो मिलियन अंकों के साथ दो अंकों के साथ देखा है, दूसरा शब्द (2 एन) महत्वहीन हो जाता है (उस चरण तक कुल संचालन के 0.0002% के लिए लेखांकन)।

कोई यह देख सकता है कि हमने यहां सबसे खराब स्थिति परिदृश्य माना है। 6 अंकों की संख्या गुणा करते समय उनमें से एक 4 अंक है और दूसरा 6 अंक है, तो हमारे पास केवल 24 गुणा हैं। फिर भी हम उस 'एन' के लिए सबसे खराब केस परिदृश्य की गणना करते हैं, यानी जब दोनों 6 अंक संख्याएं होती हैं। इसलिए बिग-ओ नोटेशन एल्गोरिदम के सबसे खराब स्थिति के बारे में है

टेलीफोन बुक

अगले सबसे अच्छे उदाहरण के बारे में मैं सोच सकता हूं कि टेलीफोन बुक, जिसे आमतौर पर व्हाइट पेज या समान कहा जाता है लेकिन यह देश से देश में अलग-अलग होगा। लेकिन मैं उस व्यक्ति के बारे में बात कर रहा हूं जो उपनाम द्वारा लोगों को सूचीबद्ध करता है और फिर प्रारंभिक या पहला नाम, संभावित रूप से पता और फिर टेलीफोन नंबर।

अब अगर आप एक कंप्यूटर पुस्तक में "जॉन स्मिथ" के लिए फोन नंबर देखने के लिए निर्देश दे रहे थे जिसमें 1,000,000 नाम हैं, तो आप क्या करेंगे? इस तथ्य को अनदेखा करते हुए कि आप अनुमान लगा सकते हैं कि एस के शुरू में कितना दूर है (मान लीजिए कि आप नहीं कर सकते), आप क्या करेंगे?

एक सामान्य कार्यान्वयन मध्य तक खुल सकता है, 500,000 वें ले सकता है और इसे "स्मिथ" से तुलना कर सकता है। यदि यह "स्मिथ, जॉन" होता है, तो हम वास्तव में असली भाग्यशाली हो गए। अधिक संभावना है कि "जॉन स्मिथ" उस नाम से पहले या उसके बाद होगा। यदि हम इसके बाद फोन बुक के आखिरी हिस्से को आधे में विभाजित करते हैं और दोहराते हैं। यदि यह पहले है तो हम आधे फोन में फोन बुक के पहले भाग को विभाजित करते हैं और दोहराते हैं। और इसी तरह।

इसे बाइनरी सर्च कहा जाता है और प्रोग्रामिंग में हर दिन इसका इस्तेमाल किया जाता है चाहे आप इसे महसूस करें या नहीं।

इसलिए यदि आप लाखों नामों की फोन बुक में कोई नाम ढूंढना चाहते हैं तो आप वास्तव में इसे 20 बार कर कर कोई नाम ढूंढ सकते हैं। खोज एल्गोरिदम की तुलना में हम तय करते हैं कि यह तुलना हमारी 'एन' है।

  • 3 नामों की एक फोन बुक के लिए इसमें 2 तुलना (अधिकतर) होती है।
  • 7 के लिए यह अधिकतम 3 लेता है।
  • 15 के लिए यह 4 लेता है।
  • ...
  • 1,000,000 के लिए यह 20 लेता है।

यह आश्चर्यजनक रूप से अच्छा नहीं है?

बिग-ओ शब्दों में यह ओ (लॉग एन) या लॉगरिदमिक जटिलता है । अब प्रश्न में लॉगरिदम एलएन (बेस ई), लॉग 10 , लॉग 2 या कुछ अन्य आधार हो सकता है। इससे कोई फर्क नहीं पड़ता कि यह अभी भी ओ (लॉग एन) है जैसे ओ (2 एन 2 ) और ओ ( 100 एन 2 ) अभी भी ओ (एन 2 ) दोनों हैं।

इस बिंदु पर यह समझाया जा सकता है कि बिग ओ का उपयोग एल्गोरिदम के साथ तीन मामलों को निर्धारित करने के लिए किया जा सकता है:

  • सर्वश्रेष्ठ मामला: टेलीफोन बुक सर्च में, सबसे अच्छा मामला यह है कि हमें एक तुलना में नाम मिलता है। यह ओ (1) या निरंतर जटिलता है ;
  • अपेक्षित मामला: जैसा कि ऊपर चर्चा की गई है ओ (लॉग एन) है; तथा
  • सबसे खराब मामला: यह भी ओ (लॉग एन) है।

आम तौर पर हमें सबसे अच्छे मामले की परवाह नहीं है। हम अपेक्षित और सबसे खराब मामले में रुचि रखते हैं। कभी-कभी इनमें से एक या दूसरा अधिक महत्वपूर्ण होगा।

टेलीफोन बुक पर वापस।

क्या होगा यदि आपके पास फ़ोन नंबर है और आप कोई नाम ढूंढना चाहते हैं? पुलिस के पास एक रिवर्स फोन बुक है लेकिन आम लोगों को इस तरह के लुक-अप से इनकार किया जाता है। या क्या वे? तकनीकी रूप से आप सामान्य फोन बुक में एक नंबर को देख सकते हैं। कैसे?

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

तो फोन नंबर (रिवर्स लुकअप) दिए गए नाम को ढूंढने के लिए:

  • सर्वश्रेष्ठ मामला: ओ (1);
  • अपेक्षित मामला: ओ (एन) (500,000 के लिए); तथा
  • सबसे खराब मामला: ओ (एन) (1,000,000 के लिए)।

यात्रा विक्रेता

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

सरल लगता है? फिर से विचार करना।

यदि आपके पास सभी जोड़े के बीच सड़कों के साथ 3 कस्बों ए, बी और सी हैं तो आप जा सकते हैं:

  • ए → बी → सी
  • ए → सी → बी
  • बी → सी → ए
  • बी → ए → सी
  • सी → ए → बी
  • सी → बी → ए

वैसे वास्तव में इससे कम है क्योंकि इनमें से कुछ बराबर हैं (ए → बी → सी और सी → बी → ए समकक्ष हैं, उदाहरण के लिए, क्योंकि वे एक ही सड़कों का उपयोग करते हैं, बस विपरीत में)।

वास्तविकता में 3 संभावनाएं हैं।

  • इसे 4 शहरों में ले जाएं और आपके पास (iirc) 12 संभावनाएं हैं।
  • 5 के साथ यह 60 है।
  • 6 360 हो जाता है।

यह एक फैक्टोरियल नामक गणितीय ऑपरेशन का एक कार्य है। मूल रूप से:

  • 5! = 5 × 4 × 3 × 2 × 1 = 120
  • 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
  • 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
  • ...
  • 25! = 25 × 24 × ... × 2 × 1 = 15,511,210,043,330,985,984,000,000
  • ...
  • 50! = 50 × 49 × ... × 2 × 1 = 3.04140932 × 10 64

तो ट्रैवलिंग सेल्समैन समस्या का बिग-ओ ओ (एन!) या फैक्टोरियल या संयोजक जटिलता है

जब तक आप 200 शहरों तक पहुंच जाते हैं तब तक पारंपरिक कंप्यूटरों के साथ समस्या को हल करने के लिए ब्रह्मांड में पर्याप्त समय नहीं बचा है।

कुछ चीजें सोचने के लिये।

बहुपदी समय फलन

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

ओ (एन), ओ (एन 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 नहीं हो सकता है या जो भी वे कहते हैं, लेकिन यह स्केलिंग में हावी कारक होगा।


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

जब हम एल्गोरिदम के बारे में बात करते हैं तो 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


एल्गोरिदम उदाहरण (जावा):

// given a list of integers L, and an integer K
public boolean simple_search(List<Integer> L, Integer K)
{
    // for each integer i in list L
    for (Integer i : L)
    {
        // if i is equal to K
        if (i == K)
        {
            return true;
        }
    }

    return false;
}

एल्गोरिदम विवरण:

  • यह एल्गोरिदम एक सूची खोजता है, वस्तु द्वारा आइटम, एक कुंजी की तलाश में,

  • सूची में प्रत्येक आइटम पर इटरेट करना, यदि यह कुंजी है तो सत्य लौटें,

  • यदि लूप कुंजी खोजने के बिना समाप्त हो गया है, तो झूठी वापसी करें।

बिग-ओ नोटेशन कॉम्प्लेक्सिटी (टाइम, स्पेस, ..) पर ऊपरी बाउंड का प्रतिनिधित्व करता है।

टाइम कॉम्प्लेक्सिटी पर द बिग-ओ ढूंढने के लिए:

  • सबसे खराब केस लेने में कितना समय (इनपुट आकार के संबंध में) की गणना करें:

  • सबसे खराब मामला: कुंजी सूची में मौजूद नहीं है।

  • समय (सबसे खराब मामला) = 4 एन + 1

  • समय: ओ (4 एन + 1) = ओ (एन) | बिग-ओ में, स्थिरांक उपेक्षित हैं

  • ओ (एन) ~ रैखिक

बिग-ओमेगा भी है, जो बेस्ट केस की जटिलता का प्रतिनिधित्व करता है:

  • बेस्ट केस: कुंजी पहला आइटम है।

  • समय (सर्वश्रेष्ठ केस) = 4

  • समय: Ω (4) = ओ (1) ~ त्वरित \ Constant


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

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

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

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

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


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

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


ठीक है, मेरे 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 ) के रूप में व्यक्त किया गया है


बिग ओ एक माप है कि एल्गोरिदम अपने इनपुट के आकार के सापेक्ष कितना समय / स्थान उपयोग करता है।

यदि एक एल्गोरिदम ओ (एन) है तो समय / स्थान इसके इनपुट के समान दर पर बढ़ेगा।

यदि एक एल्गोरिदम ओ (एन 2 ) है तो उसके इनपुट वर्ग की दर से समय / स्थान बढ़ता है।

और इसी तरह।


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

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

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

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

मेरी सूची

  1. 1
  2. 6
  3. 3

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

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

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

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

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


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

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

और इसके अलावा

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

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

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

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

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


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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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


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


मान लें कि हम एल्गोरिदम ए के बारे में बात कर रहे हैं , जो आकार n के डेटासेट के साथ कुछ करना चाहिए ।

फिर O( <some expression X involving n> )मतलब है, सरल अंग्रेजी में:

यदि आप ए को निष्पादित करते समय दुर्भाग्यपूर्ण हैं, तो यह एक्स (एन) संचालन को पूरा करने में लग सकता है।

जैसे ही होता है, कुछ कार्य होते हैं (उनके बारे में एक्स (एन) के कार्यान्वयन के रूप में सोचें ) जो अक्सर होते हैं। ये अच्छी तरह से जाना जाता है और आसानी से तुलना कर रहे हैं (उदाहरण: , , , , , आदि ..)1Log NNN^2N!

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

आम तौर पर, हमारा लक्ष्य एल्गोरिदम को इस तरह से ढूंढना या संरचना करना होगा कि इसमें एक ऐसा कार्य होगा जो X(n)जितना संभव हो उतना कम हो।


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

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

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

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

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

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

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

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

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


समय जटिलता की गणना के लिए समय की जटिलता को समझने के लिए मेरे पास सबसे आसान तरीका है बिग ओ नोटेशन। यह सभी निरंतर कारकों को हटा देता है ताकि एन के संबंध में चलने का समय अनुमान लगाया जा सके क्योंकि एन अनंतता तक पहुंचता है। आम तौर पर आप इस तरह सोच सकते हैं:

statement;

स्थिर है कथन का चलने का समय एन के संबंध में नहीं बदलेगा

for ( i = 0; i < N; i++ )
  statement;

रैखिक है लूप का चलने का समय एन के लिए सीधे आनुपातिक होता है। जब एन युगल होता है, तो चलने का समय भी होता है।

for ( i = 0; i < N; i++ ) 
{
for ( j = 0; j < N; j++ )
  statement;
}

वर्गवार है दो loops के चलने का समय एन के वर्ग के लिए आनुपातिक है। जब एन युगल, एन * एन द्वारा चलने का समय बढ़ता है।

while ( low <= high ) 
{
 mid = ( low + high ) / 2;
 if ( target < list[mid] )
 high = mid - 1;
 else if ( target > list[mid] )
  low = mid + 1;
else break;
}

लॉगरिदमिक है एल्गोरिदम का चलने का समय एन द्वारा विभाजित किया जा सकता है, जिसे एन 2 से विभाजित किया जा सकता है। ऐसा इसलिए है क्योंकि एल्गोरिदम प्रत्येक पुनरावृत्ति के साथ कामकाजी क्षेत्र को आधा में विभाजित करता है।

void quicksort ( int list[], int left, int right )
{
  int pivot = partition ( list, left, right );
  quicksort ( list, left, pivot - 1 );
  quicksort ( list, pivot + 1, right );
}

एन * लॉग (एन) है। चलने वाले समय में एन लूप (पुनरावृत्ति या पुनरावर्ती) होते हैं जो लॉगरिदमिक होते हैं, इस प्रकार एल्गोरिदम रैखिक और लॉगरिदमिक का संयोजन होता है।

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

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





time-complexity