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


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


4533
2018-01-28 11:10


मूल


सारांश: एल्गोरिदम की जटिलता की ऊपरी सीमा। इसी तरह के सवाल भी देखें बिग ओ, आप इसकी गणना कैसे / अनुमानित करते हैं? एक अच्छी व्याख्या के लिए। - Kosi2801
अन्य उत्तरों काफी अच्छे हैं, इसे समझने के लिए केवल एक विवरण: ओ (लॉग एन) या इसी तरह के माध्यम से, यह इनपुट की "लंबाई" या "आकार" पर निर्भर करता है, न कि मूल्य पर। यह समझना मुश्किल हो सकता है, लेकिन यह बहुत महत्वपूर्ण है। उदाहरण के लिए, ऐसा तब होता है जब आपका एल्गोरिदम प्रत्येक पुनरावृत्ति में दो में चीजों को विभाजित कर रहा है। - Harald Schilly
एमआईटी के व्याख्यान 8 में एल्गोरिदम की जटिलता के लिए समर्पित एक व्याख्यान है "कंप्यूटर विज्ञान और प्रोग्रामिंग परिचय" पाठ्यक्रम youtube.com/watch?v=ewd7Lf2dr5Q यह पूरी तरह से अंग्रेजी नहीं है, लेकिन आसानी से समझने योग्य उदाहरणों के साथ अच्छी व्याख्या देता है। - ivanjovanovic
बिग ओ एक समारोह के सबसे बुरे केस प्रदर्शन का अनुमान है, यह मानते हुए कि एल्गोरिदम अधिकतम संख्या में पुनरावृत्तियों का प्रदर्शन करेगा। - Paul Sweatte
Big-O notation explained by a self-taught programmer - Soner Gönül


जवाब:


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


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

Big O Analysis

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

अस्थिर ने महसूस किया होगा कि हम परिचालन की संख्या को व्यक्त कर सकते हैं: एन2 + 2 एन। लेकिन जैसा कि आपने हमारे उदाहरण से दो मिलियन अंकों के साथ दो अंकों के साथ देखा है, दूसरा शब्द (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 × 1064

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

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

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

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

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

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

वैसे भी, यह मेरे (आशावादी सादे अंग्रेजी) बिग ओ (संशोधित) के स्पष्टीकरण के लिए है।


6094
2018-01-28 11:18



जबकि अन्य उत्तर ओ (1), ओ (एन ^ 2) एट अल के बीच मतभेदों को समझाने पर ध्यान केंद्रित करते हैं .... आपका वह है जो बताता है कि कैसे एल्गोरिदम को एन ^ 2, एनएलओएल (एन) आदि में वर्गीकृत किया जा सकता है। + 1 एक अच्छे उत्तर के लिए जिसने मुझे बिग ओ नोटेशन को समझने में मदद की - Yew Long
कोई यह जोड़ना चाहता है कि बड़ा-ओ ऊपरी बाउंड (एल्गोरिदम द्वारा दिया गया) का प्रतिनिधित्व करता है, बड़े-ओमेगा एक कम बाध्य (आमतौर पर एक विशिष्ट एल्गोरिदम से स्वतंत्र प्रमाण के रूप में दिया जाता है) और बड़े-थेटा का अर्थ है कि "इष्टतम" एल्गोरिदम उस निचले बाउंड तक पहुंच जाना ज्ञात है। - mdm
यह अच्छा है यदि आप सबसे लंबे उत्तर की तलाश में हैं, लेकिन उस उत्तर के लिए नहीं जो सर्वोत्तम तरीके से बिग-ओ को समझाता है। - kirk.burleson
-1: यह बेहद गलत है: _ "बिगओह एल्गोरिदम की जटिलता का सापेक्ष प्रतिनिधित्व है"। नहीं। बिगओह एक एसिम्प्टोटिक ऊपरी सीमा है और कंप्यूटर विज्ञान से काफी अच्छी तरह से स्वतंत्र है। ओ (एन) रैखिक है। नहीं, आप थिटा के साथ बिगओह को भ्रमित कर रहे हैं। लॉग एन ओ (एन) है। 1 ओ (एन) है। इस उत्तर (और टिप्पणियों) के लिए उपेक्षा की संख्या, जो बिगओह के साथ थेटा को भ्रमित करने की मूल गलती को काफी शर्मनाक है ...
"जब तक आप 200 शहरों तक पहुंच जाते हैं तब तक पारंपरिक कंप्यूटरों के साथ समस्या को हल करने के लिए ब्रह्मांड में पर्याप्त समय नहीं बचा है।"जब ब्रह्मांड खत्म होने जा रहा है? - Isaac


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

पर2): जाना जाता है Quadratic जटिलता

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

ध्यान दें कि वस्तुओं की संख्या 10 के कारक से बढ़ जाती है, लेकिन समय 10 के कारक से बढ़ता है2। असल में, एन = 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

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


662
2018-01-28 11:28



इस परिभाषा का क्या अर्थ है? (वस्तुओं की संख्या अभी भी 10 के कारक से बढ़ रही है, लेकिन ओ (1) का स्केलिंग कारक हमेशा होता है 1.) - HollerTrain
सेकंड नहीं, संचालन। इसके अलावा, आप फैक्टोरियल और लॉगरिदमिक समय पर चूक गए। - Chris Charabaruk
यह बहुत अच्छी तरह से व्याख्या नहीं करता है कि ओ (एन ^ 2) एक एल्गोरिदम का वर्णन कर सकता है जो सटीक रूप से चलता है .01 * एन ^ 2 + 99 99 99 * एन + 99 99 99. यह जानना महत्वपूर्ण है कि इस पैमाने का उपयोग करके एल्गोरिदम की तुलना की जाती है, और तुलना तब होती है जब एन 'पर्याप्त रूप से बड़ा' होता है। पाइथन का समय वास्तव में छोटे सरणी के लिए सम्मिलन क्रम (सबसे खराब / औसत मामला ओ (एन ^ 2)) का उपयोग करता है क्योंकि इस तथ्य के कारण कि इसका एक छोटा ओवरहेड है। - Darthfett
यह जवाब बड़े ओ नोटेशन और थेटा नोटेशन को भी भ्रमित करता है। एन का कार्य जो उसके सभी इनपुट (आमतौर पर केवल 1 के रूप में लिखा जाता है) के लिए 1 देता है वास्तव में ओ (एन ^ 2) में होता है (भले ही यह ओ (1) में भी हो)। इसी प्रकार, एक एल्गोरिदम जिसे केवल एक चरण करना होता है जो लगातार समय लेता है उसे ओ (1) एल्गोरिदम भी माना जाता है, लेकिन यह ओ (एन) और ओ (एन ^ 2) एल्गोरिदम भी होता है। लेकिन शायद गणितज्ञ और कंप्यूटर वैज्ञानिक परिभाषा पर सहमत नहीं हैं: - /। - Jacob Akkerboom
ओ (लॉग एन) इस उत्तर में माना जाने वाला लॉगरिदमिक जटिलता आधार 10 का है। आम तौर पर मानक आधार 2 के साथ गणना करना है। किसी को इस तथ्य को ध्यान में रखना चाहिए और भ्रमित नहीं होना चाहिए। जैसा कि @ChrisCharabaruk द्वारा वर्णित है जटिलता संचालन की संख्या दर्शाती है और सेकंड नहीं। - Aksh1801


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


मूल बातें

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

  • f(x) ∈ O(upperbound) माध्यम f "से तेज नहीं बढ़ता" upperbound
  • f(x) ∈ Ɵ(justlikethis) मतलब f "बिल्कुल बढ़ता है" justlikethis
  • f(x) ∈ Ω(lowerbound) माध्यम f "से धीमी गति से बढ़ता है" lowerbound

बड़े-ओ नोटेशन निरंतर कारकों की परवाह नहीं करता है: कार्य 9x² कहा जाता है "बिल्कुल ठीक हो जाना" 10x²। न तो बड़ा-ओ करता है asymptotic के बारे में नोटेशन देखभाल गैर asymptotic सामान ("मूल के पास सामान" या "समस्या का आकार छोटा होने पर क्या होता है"): फ़ंक्शन 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)         

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

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


अनुप्रयोगों

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

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

उदाहरण

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

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

everyone handshakes everyone else. Image credit and license per wikipedia/wikimedia commons "complete graph" article.  adjacency matrix

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

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

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

("सादे अंग्रेजी" से अस्थायी 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 ...


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

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

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


362
2017-07-08 04:46



एक उत्कृष्ट गणितीय उत्तर, लेकिन ओपी ने एक सादे अंग्रेजी उत्तर के लिए कहा। गणितीय विवरण के इस स्तर को उत्तर को समझने की आवश्यकता नहीं है, हालांकि लोगों के लिए विशेष रूप से गणितीय रूप से दिमाग में यह "सादे अंग्रेजी" से समझने के लिए बहुत आसान हो सकता है। हालांकि ओपी ने बाद के लिए पूछा। - El Zorko
संभावित रूप से ओपी के अलावा अन्य लोगों को इस प्रश्न के उत्तर में रुचि हो सकती है। क्या यह साइट का मार्गदर्शक सिद्धांत नहीं है? - Casey
जबकि मैं शायद देख सकता हूं कि क्यों लोग मेरे जवाब को स्किम कर सकते हैं और सोचते हैं कि यह बहुत मैथी है (विशेष रूप से "गणित नया सादा अंग्रेजी" स्नैप टिप्पणियां हटा दी गई है), मूल प्रश्न बड़े-ओ के बारे में पूछता है जो कार्यों के बारे में है, इसलिए मैं स्पष्ट होने और कार्यों के बारे में बात करने का प्रयास करें जो सादे-अंग्रेज़ी अंतर्ज्ञान को पूरा करता है। यहां गणित को अक्सर उच्च विद्यालय गणित पृष्ठभूमि के साथ चमक या समझा जा सकता है। मुझे लगता है कि लोग अंत में गणित ऐडेंडा को देख सकते हैं, और मान लें कि यह उत्तर का हिस्सा है, जब यह देखने के लिए केवल वहां है कि क्या असली गणित की तरह दिखता है। - ninjagecko
यह एक शानदार जवाब है; सबसे अधिक वोट वाले एक से बेहतर आईएमओ। आवश्यक "गणित" "ओ" के बाद कोष्ठक में अभिव्यक्तियों को समझने के लिए आवश्यक चीज़ों से परे नहीं जाता है, जो किसी भी उदाहरण का उपयोग करने वाले उचित स्पष्टीकरण से बच सकता है। - Dave Abrahams
"एफ (एक्स) ∈ ओ (ऊपरीबाउंड) का मतलब है" एफ "ऊपरी" से तेज़ नहीं होता है, इन तीनों को आसानी से लिखा गया है, लेकिन बड़े ओह, थेटा और ओमेगा के गणितीय रूप से उचित स्पष्टीकरण सुनहरे हैं। उन्होंने मुझे सादे अंग्रेजी में बताया कि जटिल गणितीय अभिव्यक्तियों को लिखे बिना 5 अलग-अलग स्रोत मुझे अनुवाद नहीं कर पाए। धन्यवाद दोस्त! :) - timbram


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

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

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

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

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

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

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

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

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


237
2018-01-28 11:16



एक हैशटेबल को वास्तविक सरणी (कार्यान्वयन के आधार पर) की अनुक्रमणिका की गणना करने के लिए चलाने के लिए एक एल्गोरिदम की आवश्यकता होती है। और एक सरणी में सिर्फ ओ (1) है क्योंकि यह सिर्फ एक एड्रेस है। लेकिन इस सवाल के साथ कुछ भी नहीं है, सिर्फ एक अवलोकन :) - Filip Ekberg
जोन की व्याख्या मुझे लगता है कि सवाल के साथ बहुत ज्यादा है। यह ठीक है कि कोई इसे किसी मां को कैसे समझा सकता है, और वह अंततः इसे समझती है मुझे लगता है :) मुझे कपड़ों का उदाहरण पसंद है (विशेष रूप से आखिरी, जहां यह जटिलता की घातीय वृद्धि को बताता है) - Johannes Schaub - litb
Filip: मैं इंडेक्स द्वारा एक सरणी पते के बारे में बात नहीं कर रहा हूँ, मैं एक सरणी में एक मिलान प्रविष्टि खोजने के बारे में बात कर रहा हूँ। क्या आप जवाब दोबारा पढ़ सकते हैं और देख सकते हैं कि यह अभी भी अस्पष्ट है? - Jon Skeet
@ फिलिप एकबर्ग मुझे लगता है कि आप डायरेक्ट-एड्रेस टेबल के बारे में सोच रहे हैं, जहां प्रत्येक इंडेक्स सीधे कुंजी पर मैप्स करता है इसलिए ओ (1) है, हालांकि मुझे लगता है कि जॉन कुंजी / वैल जोड़े की एक अनारक्षित सरणी के बारे में बात कर रहा है जिसे आपको खोजना है रैखिक रूप से के माध्यम से। - ljs
@ आरबीटी: नहीं, यह एक बाइनरी लुकअप नहीं है। यह सही हैश पर जा सकता है बाल्टी तुरंत, हैश कोड से बाल्टी इंडेक्स में परिवर्तन के आधार पर। उसके बाद, बाल्टी में सही हैश कोड ढूंढना रैखिक हो सकता है या यह एक बाइनरी खोज हो सकता है ... लेकिन उस समय तक आप शब्दकोश के कुल आकार के बहुत छोटे अनुपात में हैं। - Jon Skeet


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

उदाहरण:

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

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

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

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

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


120
2018-01-28 11:23



गलत! उदाहरण के लिए ओ (एन): यदि मैं इनपुट आकार को दोगुना करता हूं तो रनटाइम शून्य शून्य स्थिरता को सीमित करने के लिए गुणा करेगा। मेरा मतलब है ओ (एन) = ओ (एन + एन) - arena-ru
मैं f (n) = O (g (n)) में f के बारे में बात कर रहा हूं, जैसा कि आपको समझ में नहीं आता है। - starblue
मैं उभरा, लेकिन आखिरी वाक्य में मुझे ज्यादा योगदान नहीं होता है। बिग (ओ) पर चर्चा या मापते समय हम अक्सर "बिट्स" के बारे में बात नहीं करते हैं। - cdiggins
आपको ओ (एन लॉग एन) के लिए एक उदाहरण जोड़ना चाहिए। - Christoffer Hammarström
यह इतना स्पष्ट नहीं है, अनिवार्य रूप से यह ओ (एन) से थोड़ा बदतर व्यवहार करता है। तो अगर एन डबल्स, रनटाइम को 2 से अधिक बड़े कारक से गुणा किया जाता है। - starblue


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

बिग ओ तुलना करने के लिए उपयोगी है कि कितनी अच्छी तरह से दो एल्गोरिदम स्केल हो जाएंगे क्योंकि इनपुट की संख्या बढ़ जाती है।

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

कई मामलों में एल्गोरिदम का "ओ" निम्नलिखित मामलों में से एक में आ जाएगा:

  • हे (1) - पूरा करने का समय इनपुट सेट के आकार के बावजूद समान है। एक उदाहरण इंडेक्स द्वारा सरणी तत्व का उपयोग कर रहा है।
  • हे (लॉग एन) - लॉग 2 (एन) के साथ मोटे तौर पर बढ़ने का समय। उदाहरण के लिए 1024 आइटम 32 आइटम तक लगभग दोगुना लेते हैं, क्योंकि लॉग 2 (1024) = 10 और लॉग 2 (32) = 5. एक उदाहरण में एक आइटम ढूंढ रहा है बाइनरी खोज पेड़ (BST)।
  • पर) - इनपुट सेट के आकार के साथ रैखिक रूप से उस पैमाने को पूरा करने का समय। दूसरे शब्दों में यदि आप इनपुट सेट में आइटम्स की संख्या को दोगुना करते हैं, तो एल्गोरिदम लगभग दोगुना होता है। एक उदाहरण एक लिंक्ड सूची में वस्तुओं की संख्या गिन रहा है।
  • ओ (एन लॉग एन) - लॉग 2 (एन) के परिणाम आइटम की संख्या से बढ़ने का समय। इसका एक उदाहरण है ढेर बनाएं और छांटें तथा जल्दी से सुलझाएं
  • हे (एन ^ 2) - पूरा करने का समय लगभग वस्तुओं की संख्या के वर्ग के बराबर है। इसका एक उदाहरण है बबल शॅाट
  • पर!) - पूरा करने का समय इनपुट सेट का फैक्टोरियल है। इसका एक उदाहरण है यात्रा विक्रेता समस्या क्रूर बल समाधान

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


97
2017-09-05 16:31



cdiggins, अगर मेरे पास ओ (एन / 2) जटिलता है, तो यह ओ (एन) या ओ (एन / 2) होना चाहिए, उदाहरण के लिए जटिलता अगर मैं आधे स्ट्रिंग पर लूप करूंगा। - Melad Ezzat
@Melad यह एक निरंतर (0.5) फ़ंक्शन में गुणा होने का एक उदाहरण है। इसे अनदेखा किया जाता है क्योंकि इसे एन के बहुत बड़े मूल्यों के लिए सार्थक प्रभाव माना जाता है। - cdiggins


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

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

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

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

मेरी सूची

  1. 1
  2. 6
  3. 3

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

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

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

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

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


77
2018-01-28 11:14



लॉगऑन के लिए हम 0 से एन / 2 से चल रहे लूप के लिए ओ (लॉग लॉग एन) के बारे में क्या सोचते हैं? मेरा मतलब है कि प्रोग्राम कैसा दिखता है? शुद्ध गणित कौशल के लिए मुझे माफ़ कर दो - Pablo Escobar