क्या हे कहाँ खोजने के लिए (एन^2) और हे (एन) आदि मतलब है?

Question

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

Answer 1

अंकन Big O notation कहा जाता है, और एल्गोरिथम जटिलता को व्यक्त करने के लिए एक आशुलिपि के रूप में प्रयोग किया जाता है यही कारण है कि (मूल रूप से कितनी देर तक एक दिया algorithim इनपुट आकार के रूप में चलाने के लिए ले जाएगा (एन) बढ़ता है)

सामान्य शब्दों में, आप करेंगे algorithims के निम्नलिखित प्रमुख प्रकार में चलाएँ:

1. हे (1) - लगातार - समय की लंबाई है कि इस algorithim पूरा करने के लिए ले जाता है आइटम है कि algorithim कार्रवाई करने के लिए है की संख्या पर निर्भर नहीं है।
2. ओ (लॉग एन) - लॉगरिदमिक - इस एल्गोरिदम को पूरा करने के लिए समय की लंबाई एल्गोरिदम को संसाधित करने वाली वस्तुओं की संख्या पर निर्भर करती है। चूंकि इनपुट आकार बड़ा हो जाता है, प्रत्येक नए इनपुट के लिए कम समय की आवश्यकता होती है।
3. ओ (एन) - रैखिक - इस एल्गोरिदम को पूरा करने के लिए समय की लंबाई सीधे एल्गोरिदम को संसाधित करने वाली वस्तुओं की संख्या पर निर्भर करती है। जैसे-जैसे इनपुट आकार बढ़ता है, उतना ही समय बराबर मात्रा में बढ़ता है।
4. ओ (एन^2) - बहुपद - जैसे इनपुट आकार बढ़ता है, इनपुट को संसाधित करने में लगने वाला समय बड़ी और बड़ी राशि से बढ़ता है - जिसका अर्थ है कि बड़े इनपुट आकार को हल करना मुश्किल हो जाता है।
5. हे (2^n) - घातीय - समस्याओं का सबसे जटिल प्रकार के। एक चरम डिग्री के लिए इनपुट आकार के आधार पर बढ़ने की प्रक्रिया।

आम तौर पर आप इसका उपयोग करके यह देखकर एल्गोरिदम की जटिलता का मोटा गेज प्राप्त कर सकते हैं।

• एक चर बुलाया राशि
• प्रारंभ एक चर मैं बुलाया प्रारंभ
• के लिए:

  function sum(int[] x) { 
      int sum = 0; 
      for (int i = 0; i < x.length; i++) { 
       sum += x[i]; 
      } 
      return sum; 
  } 
  

  कुछ चीजें है कि यहाँ किया जाना है: उदाहरण के लिए, निम्न विधि को देख i का प्रत्येक पुनरावृत्ति: एक्स [i] योग जोड़ने के लिए, 1 में जोड़ें, जांचें कि मैं x से कम है या नहीं।लंबाई

• वापसी राशि

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

Answer 2

पढ़ें के बारे में Computational Complexity पहले, तो कुछ किताबें Introduction to Algorithms तरह एल्गोरिदम के बारे में प्रयास करें।

विकिपीडिया पृष्ठ से

:

बिग ओ अंकन उनके विकास दर के अनुसार कार्यों की विशेषता

आपको जानकारी और गहराई में जाने से काम नहीं चलेगा नहीं करने के लिए, तो आप कर सकते हैं के द्वारा बहुत बार अनुमानित एल्गोरिथ्म जटिलता अपने कोड analizing:

void simpleFunction(arg); // O(1) - if number of function instructions is constant and don't depend on number of input size 

for (int i=0;i<n;i++) {simpleFunction(element[i]);} // O(n) 

for (int i=0;i<n;i++) { // this one runs O(n^2) 
    for (int j=0;j<n;j++) { 
     simpleFunction(element[i]); 
    } 
} 

for (int i=0;i<n;i*=2) { // O(lgn) 
    simpleFunction(element[i]); 
} 

कभी कभी

यह है तो सफलता में समारोह/एल्गोरिथ्म बड़ा हे संकेतन जटिलता अनुमान लगाने के लिए आसान नहीं एच मामले amortized analysis का उपयोग किया जाता है। उपरोक्त कोड केवल quickstarter के रूप में सेवा करनी चाहिए।

Answer 3

यह Big O notation कहा जाता है और एल्गोरिदम की जटिलता यों किया जाता है।

हे (1) का मतलब है एल्गोरिथ्म कोई फर्क नहीं पड़ता वहाँ कार्रवाई करने के लिए है कितना डेटा एक निरंतर समय लगता है।

हे (एन) एल्गोरिथ्म गति डेटा की मात्रा के साथ एक रैखिक तरह से बढ़ता है का मतलब है।

और इतने पर ...

तो कम हे संकेतन में की घात n बेहतर अपने एल्गोरिथ्म समस्या को हल करने के लिए है। सर्वश्रेष्ठ मामला ओ (1) (एन = 0) है। लेकिन कई समस्याओं में एक अंतर्निहित जटिलता है ताकि आपको लगभग सभी मामलों में ऐसा आदर्श एल्गोरिदम नहीं मिलेगा।

Answer 4

जवाब अब तक अच्छे हैं। वेब खोज पर मुख्य शब्द "बिग ओ नोटेशन" है।

"कुछफॉर्मुला ओ (कभी-कभी)" के गणित के पीछे मूल विचार यह है कि, जैसे आपका चर अनंतता तक जाता है, "कभी-कभी" उस सूत्र का हिस्सा होता है जो प्रभुत्व करता है।

उदाहरण के लिए, मान लें कि आपके 0.05*x^3 + 300*x^2 + 200000000*x + 10 है। एक्स (x == 1 या x == 2) के बहुत कम आकार के लिए, 200000000*x अब तक का सबसे बड़ा हिस्सा होगा। उस समय सूत्र का एक साजिश रैखिक दिखाई देगा। जैसा कि आप साथ जाते हैं, किसी बिंदु पर 300*x^2 हिस्सा बड़ा होगा। हालांकि, अगर आप भी बड़ा एक्स, बड़ा के रूप में के रूप में आप के लिए परवाह बनाने रखने के लिए, 0.05*x^3 हिस्सा सबसे बड़ा हो जाएगा, और अंत में पूरी तरह से सूत्र के अन्य भागों को भी पीछे छोड़ देगा। यही वह जगह है जहां यह एक ग्राफ से स्पष्ट हो जाता है जिसे आप एक क्यूबड फ़ंक्शन पर देख रहे हैं। तो हम कहेंगे कि सूत्र O(x^3) है।