algorithm - बिग ओ, आप इसकी गणना कैसे / अनुमानित करते हैं?




optimization complexity-theory big-o performance (19)

यदि आप कोड का विश्लेषण करके अपने कोड के क्रमशः अनुभव के अनुमान का आकलन करना चाहते हैं, तो आप अपने कोड के एन और समय के बढ़ते मूल्यों की श्रृंखला में रह सकते हैं। लॉग समय पर अपना समय प्लॉट करें। यदि कोड ओ (x ^ n) है, मान ढलान एन की रेखा पर गिरना चाहिए।

कोड का अध्ययन करने के कई फायदे हैं। एक बात के लिए, आप देख सकते हैं कि आप उस सीमा में हैं जहां रन टाइम अपने एसिम्प्टोटिक ऑर्डर तक पहुंचता है। साथ ही, आप पाएंगे कि कुछ कोड जो आपने सोचा था ओ ओ (एक्स) वास्तव में आदेश ओ (x ^ 2) है, उदाहरण के लिए, लाइब्रेरी कॉल में बिताए गए समय के कारण।

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

लेकिन मैं उत्सुक हूं, आप अपने एल्गोरिदम की जटिलता की गणना या अनुमान कैसे लगाते हैं?

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


मूल रूप से वह चीज़ जो 90% समय तक फसल करती है वह केवल लूप का विश्लेषण करती है। क्या आपके पास सिंगल, डबल, ट्रिपल नेस्टेड लूप हैं? आपके पास ओ (एन), ओ (एन ^ 2), ओ (एन ^ 3) चलने का समय है।

बहुत ही कम (जब तक आप एक व्यापक आधार पुस्तकालय (उदाहरण के लिए, .NET बीसीएल, या सी ++ एसटीएल) के साथ एक मंच लिख रहे हैं, तो आपको कुछ भी सामना करना पड़ेगा जो आपके लूप को देखने से अधिक कठिन है (बयान के लिए, जबकि, गोटो, आदि...)


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

BigOh प्राप्त करने के लिए कोई यांत्रिक प्रक्रिया नहीं है जिसका उपयोग किया जा सकता है।

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

उद्देश्य सरल है: कोड को निष्पादित करने की आवश्यकता के बिना सैद्धांतिक दृष्टिकोण से एल्गोरिदम की तुलना करना। कम संख्या में कदम, तेजी से एल्गोरिदम।

उदाहरण के लिए, मान लें कि आपके पास कोड का यह टुकड़ा है:

int sum(int* data, int N) {
    int result = 0;               // 1

    for (int i = 0; i < N; i++) { // 2
        result += data[i];        // 3
    }

    return result;                // 4
}

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

Number_Of_Steps = f(N)

तो हमारे पास f(N) , जो कम्प्यूटेशनल चरणों की संख्या को गिनने के लिए एक कार्य है। फ़ंक्शन का इनपुट प्रक्रिया के आकार की प्रक्रिया है। इसका मतलब है कि इस समारोह को इस तरह कहा जाता है:

Number_Of_Steps = f(data.length)

पैरामीटर N data.length लेता है। data.length मान। अब हमें फ़ंक्शन f() की वास्तविक परिभाषा की आवश्यकता है। यह स्रोत कोड से किया जाता है, जिसमें प्रत्येक रोचक रेखा को 1 से 4 तक गिना जाता है।

BigOh की गणना करने के कई तरीके हैं। इस बिंदु से आगे हम यह मानने जा रहे हैं कि प्रत्येक वाक्य जो इनपुट डेटा के आकार पर निर्भर नहीं है, लगातार C संख्या कम्प्यूटेशनल कदम उठाता है।

हम फ़ंक्शन के चरणों की व्यक्तिगत संख्या को जोड़ने जा रहे हैं, न तो स्थानीय परिवर्तनीय घोषणा और न ही वापसी विवरण data सरणी के आकार पर निर्भर करता है।

इसका मतलब है कि रेखा 1 और 4 प्रत्येक को सी चरणों की मात्रा लेती है, और फ़ंक्शन कुछ हद तक इस तरह है:

f(N) = C + ??? + C

अगला भाग कथन के मान को परिभाषित करना है। याद रखें कि हम कम्प्यूटेशनल चरणों की संख्या गिन रहे हैं, जिसका अर्थ है कि कथन के निकाय को N बार निष्पादित किया जाता है। C , N बार जोड़ने के समान ही है:

f(N) = C + (C + C + ... + C) + C = C + N * C + C

इस बात को गिनने के लिए कोई यांत्रिक नियम नहीं है कि कितने बार शरीर के निष्पादन को निष्पादित for जाता है, आपको यह देखने के लिए गिनना होगा कि कोड क्या करता है। गणना को सरल बनाने के लिए, हम कथन के प्रारंभिक प्रारंभिकरण, स्थिति और वृद्धि भागों को अनदेखा कर रहे हैं।

वास्तविक BigOh प्राप्त करने के लिए हमें फ़ंक्शन के असीमित विश्लेषण की आवश्यकता है। यह मोटे तौर पर ऐसा किया जाता है:

  1. सभी स्थिरांक C ले लो।
  2. f() से polynomium अपने standard form
  3. बहुपद की शर्तों को विभाजित करें और विकास की दर से उन्हें क्रमबद्ध करें।
  4. जब N infinity तो वह बड़ा हो infinity

हमारे f() में दो शर्तें हैं:

f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1

सभी C स्थिरांक और अनावश्यक भागों को दूर लेना:

f(N) = 1 + N ^ 1

चूंकि आखिरी अवधि वह है जो बड़ा हो जाता है जब f() अनंतता तक पहुंचता है ( limits पर विचार करता limits ) यह बिगऑह तर्क है, और sum() फ़ंक्शन में बिगऑह है:

O(N)

कुछ मुश्किलों को हल करने के लिए कुछ युक्तियां हैं: जब भी आप कर सकते हैं summations उपयोग करें।

उदाहरण के तौर पर, संक्षेप में इस कोड को आसानी से हल किया जा सकता है:

for (i = 0; i < 2*n; i += 2) {  // 1
    for (j=n; j > i; j--) {     // 2
        foo();                  // 3
    }
}

पहली चीज़ जो आपको पूछने की आवश्यकता है वह foo() के निष्पादन का आदेश है। जबकि सामान्य O(1) , आपको इसके बारे में अपने प्रोफेसरों से पूछना होगा। O(1) मतलब है (लगभग, ज्यादातर) स्थिर C , आकार N स्वतंत्र है।

वाक्य संख्या पर एक बयान के for मुश्किल है। जबकि सूचकांक 2 * N पर समाप्त होता है, वृद्धि दो से की जाती है। इसका मतलब है कि पहले के for केवल N कदम निष्पादित किए जाते हैं, और हमें गिनती को दो से विभाजित करने की आवश्यकता होती है।

f(N) = Summation(i from 1 to 2 * N / 2)( ... ) = 
     = Summation(i from 1 to N)( ... )

वाक्य संख्या दो भी कठिन है क्योंकि यह i मूल्य पर निर्भर करता है। एक नज़र डालें: इंडेक्स मैं मान लेता हूं: 0, 2, 4, 6, 8, ..., 2 * एन, और दूसरा निष्पादित करने के लिए: एन बार पहला, एन -2 दूसरा, एन - 4 तीसरा ... एन / 2 चरण तक, जिस पर दूसरा कभी निष्पादित नहीं होता है।

सूत्र पर, इसका मतलब है:

f(N) = Summation(i from 1 to N)( Summation(j = ???)(  ) )

फिर, हम कदमों की संख्या गिन रहे हैं। और परिभाषा के अनुसार, प्रत्येक सम्मेलन हमेशा एक से शुरू होना चाहिए, और एक से अधिक बड़े या बराबर पर समाप्त होना चाहिए।

f(N) = Summation(i from 1 to N)( Summation(j = 1 to (N - (i - 1) * 2)( C ) )

(हम मानते हैं कि foo() O(1) और C कदम उठाता है।)

हमें यहां एक समस्या है: जब i मूल्य N / 2 + 1 ऊपर लेता i , तो आंतरिक सारांश नकारात्मक संख्या पर समाप्त होता है! यह असंभव और गलत है। हमें संक्षेप में विभाजित करने की जरूरत है, जिस क्षण i N / 2 + 1 लेता i

f(N) = Summation(i from 1 to N / 2)( Summation(j = 1 to (N - (i - 1) * 2)) * ( C ) ) + Summation(i from 1 to N / 2) * ( C )

चूंकि मुख्य क्षण i > N / 2 , आंतरिक के for आंतरिक निष्पादित नहीं for जाएगा, और हम अपने शरीर पर निरंतर सी निष्पादन जटिलता मान रहे हैं।

अब कुछ पहचान नियमों का उपयोग करके सारांशों को सरल बनाया जा सकता है:

  1. सारांश (1 से एन तक डब्ल्यू) (सी) = एन * सी
  2. सारांश (1 से एन तक) (ए (+/-) बी) = सारांश (1 से एन तक) (ए) (+/-) सारांश (1 से एन तक) (बी)
  3. सारांश (1 से एन तक) (डब्ल्यू * सी) = सी * सारांश (1 से एन तक) (डब्ल्यू) (सी स्थिर है, w स्वतंत्र)
  4. सारांश (1 से एन तक) (डब्ल्यू) = (एन * (एन + 1)) / 2

कुछ बीजगणित लागू करना:

f(N) = Summation(i from 1 to N / 2)( (N - (i - 1) * 2) * ( C ) ) + (N / 2)( C )

f(N) = C * Summation(i from 1 to N / 2)( (N - (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (Summation(i from 1 to N / 2)( N ) - Summation(i from 1 to N / 2)( (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2)( i - 1 )) + (N / 2)( C )

=> Summation(i from 1 to N / 2)( i - 1 ) = Summation(i from 1 to N / 2 - 1)( i )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2 - 1)( i )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N / 2 - 1) * (N / 2 - 1 + 1) / 2) ) + (N / 2)( C )

=> (N / 2 - 1) * (N / 2 - 1 + 1) / 2 = 

   (N / 2 - 1) * (N / 2) / 2 = 

   ((N ^ 2 / 4) - (N / 2)) / 2 = 

   (N ^ 2 / 8) - (N / 4)

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N ^ 2 / 8) - (N / 4) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - ( (N ^ 2 / 4) - (N / 2) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - (N ^ 2 / 4) + (N / 2)) + (N / 2)( C )

f(N) = C * ( N ^ 2 / 4 ) + C * (N / 2) + C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + 2 * C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + C * N

f(N) = C * 1/4 * N ^ 2 + C * N

और बिग ओह है:

O(N²)

Don't forget to also allow for space complexities that can also be a cause for concern if one has limited memory resources. So for example you may hear someone wanting a constant space algorithm which is basically a way of saying that the amount of space taken by the algorithm doesn't depend on any factors inside the code.

Sometimes the complexity can come from how many times is something called, how often is a loop executed, how often is memory allocated, and so on is another part to answer this question.

Lastly, big O can be used for worst case, best case, and amortization cases where generally it is the worst case that is used for describing how bad an algorithm may be.


यदि आपकी लागत बहुपद है, तो इसके गुणक के बिना, उच्चतम आदेश अवधि रखें। उदाहरण के लिए:

ओ ((एन / 2 + 1) * (एन / 2)) = ओ (एन 2/4 + एन / 2) = ओ (एन 2/4) = ओ (एन 2 )

यह अनंत श्रृंखला के लिए काम नहीं करता है, आपको दिमाग। सामान्य मामले के लिए कोई भी नुस्खा नहीं है, हालांकि कुछ आम मामलों के लिए, निम्नलिखित असमानताएं लागू होती हैं:

ओ (लॉग एन ) <ओ ( एन ) <ओ ( एन लॉग एन ) <ओ ( एन 2 ) <ओ ( एन के ) <ओ (ई एन ) <ओ ( एन !)


What often gets overlooked is the expected behavior of your algorithms. It doesn't change the Big-O of your algorithm , but it does relate to the statement "premature optimization. . .."

Expected behavior of your algorithm is -- very dumbed down -- how fast you can expect your algorithm to work on data you're most likely to see.

For instance, if you're searching for a value in a list, it's O(n), but if you know that most lists you see have your value up front, typical behavior of your algorithm is faster.

To really nail it down, you need to be able to describe the probability distribution of your "input space" (if you need to sort a list, how often is that list already going to be sorted? how often is it totally reversed? how often is it mostly sorted?) It's not always feasible that you know that, but sometimes you do.


पहले मामले के लिए, आंतरिक लूप को ni बार निष्पादित किया जाता है, इसलिए ni 0 से n-1 (क्योंकि उससे कम, कम या बराबर नहीं) के लिए निष्पादन की कुल संख्या योग है। आप अंततः n*(n + 1) / 2 , इसलिए O(n²/2) = O(n²)

दूसरे लूप के लिए, i बाहरी लूप के लिए 0 और n बीच शामिल है; तब आंतरिक लूप निष्पादित होता है जब j कड़ाई से n से अधिक होता है, जो तब असंभव होता है।


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

अधिक जानकारी के लिए, विषय पर विकिपीडिया पेज देखें


great question!

If you're using the Big O, you're talking about the worse case (more on what that means later). Additionally, there is capital theta for average case and a big omega for best case.

Check out this site for a lovely formal definition of Big O: https://xlinux.nist.gov/dads/HTML/bigOnotation.html

f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.

Ok, so now what do we mean by "best-case" and "worst-case" complexities?

This is probably most clearly illustrated through examples. For example if we are using linear search to find a number in a sorted array then the worst case is when we decide to search for the last element of the array as this would take as many steps as there are items in the array. The best case would be when we search for the first element since we would be done after the first check.

The point of all these adjective -case complexities is that we're looking for a way to graph the amount of time a hypothetical program runs to completion in terms of the size of particular variables. However for many algorithms you can argue that there is not a single time for a particular size of input. Notice that this contradicts with the fundamental requirement of a function, any input should have no more than one output. So we come up with multiple functions to describe an algorithm's complexity. Now, even though searching an array of size n may take varying amounts of time depending on what you're looking for in the array and depending proportionally to n, we can create an informative description of the algorithm using best-case, average-case, and worst-case classes.

Sorry this is so poorly written and lacks much technical information. But hopefully it'll make time complexity classes easier to think about. Once you become comfortable with these it becomes a simple matter of parsing through your program and looking for things like for-loops that depend on array sizes and reasoning based on your data structures what kind of input would result in trivial cases and what input would result in worst-cases.


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

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

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

इसलिए हम ओ (एन * लॉग (एन)) द्वारा काम की मात्रा को ऊपरी सीमा से जोड़ सकते हैं।

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

a=0;
b=1;
for (i = 0; i <n; i++) {
    tmp = b;
    b = a + b;
    a = tmp;
}

और आइए बस ए और बी जावा में BigIntegers या कुछ ऐसा है जो मनमाने ढंग से बड़ी संख्या को संभाल सकता है। ज्यादातर लोग कहेंगे कि यह एक ओ (एन) एल्गोरिदम बिना flinching के है। तर्क यह है कि आपके पास लूप के साथ लूप और ओ (1) काम में एन पुनरावृत्तियों हैं।

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

1 + 2 + 3 + ... + एन = एन (एन -1) / 2 = ओ (एन ^ 2)

तो यह एल्गोरिदम quadradic समय में चलाता है!


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

http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions से उठाए गए कुछ सबसे आम मामले यहां दिए गए हैं:

ओ (1) - यह निर्धारित करना कि कोई संख्या भी अजीब है या नहीं; स्थिर-आकार लुकअप तालिका या हैश तालिका का उपयोग करना

ओ (लॉगऑन) - एक बाइनरी खोज के साथ एक क्रमबद्ध सरणी में एक आइटम ढूँढना

ओ (एन) - एक अपरिवर्तित सूची में एक आइटम ढूँढना; दो एन-अंक संख्या जोड़ना

ओ (एन 2 ) - एक साधारण एल्गोरिदम द्वारा दो एन-अंक संख्या गुणा करना; दो एन × एन matrices जोड़ना; बुलबुला सॉर्ट या सम्मिलन प्रकार

ओ (एन 3 ) - सरल एल्गोरिदम द्वारा दो एन × एन matrices गुणा

ओ (सी एन ) - गतिशील प्रोग्रामिंग का उपयोग कर यात्रा विक्रेता समस्या के लिए (सटीक) समाधान ढूँढना; यह निर्धारित करना कि क्या दो तार्किक बयान ब्रूट फोर्स का उपयोग कर समकक्ष हैं

हे (एन!) - ब्रूट-फोर्स सर्च के माध्यम से यात्रा विक्रेता की समस्या को हल करना

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


I don't know how to programmatically solve this, but the first thing people do is that we sample the algorithm for certain patterns in the number of operations done, say 4n^2 + 2n + 1 we have 2 rules:

  1. If we have a sum of terms, the term with the largest growth rate is kept, with other terms omitted.
  2. If we have a product of several factors constant factors are omitted.

If we simplify f(x), where f(x) is the formula for number of operations done, (4n^2 + 2n + 1 explained above), we obtain the big-O value [O(n^2) in this case]. But this would have to account for Lagrange interpolation in the program, which may be hard to implement. And what if the real big-O value was O(2^n), and we might have something like O(x^n), so this algorithm probably wouldn't be programmable. But if someone proves me wrong, give me the code . । । ।


मैं जानकारी के संदर्भ में इसके बारे में सोचता हूं। किसी भी समस्या में बिट्स की एक निश्चित संख्या सीखने के होते हैं।

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

उदाहरण के लिए, if दो शाखाएं हैं, तो दोनों शाखाओं में समान रूप से 1/2 * लॉग (2/1) + 1/2 * लॉग (2/1) = 1/2 * 1 + 1/2 * 1 = 1. तो इसकी एन्ट्रॉपी 1 बिट है।

मान लीजिए कि आप एन आइटम की एक तालिका खोज रहे हैं, जैसे एन = 1024। यह एक 10-बिट समस्या है क्योंकि लॉग (1024) = 10 बिट्स। इसलिए यदि आप इसे आईएफ स्टेटमेंट्स के साथ खोज सकते हैं जिनके पास समान रूप से संभावित परिणाम हैं, तो इसमें 10 निर्णय लेना चाहिए।

बाइनरी खोज के साथ आपको यही मिलता है।

मान लीजिए कि आप रैखिक खोज कर रहे हैं। आप पहले तत्व को देखते हैं और पूछते हैं कि यह वही है जो आप चाहते हैं। संभावनाएं 1/1024 हैं जो यह है, और 1023/1024 है कि यह नहीं है। उस निर्णय की एन्ट्रॉपी 1/1024 * लॉग (1024/1) + 1023/1024 * लॉग (1024/1023) = 1/1024 * 10 + 1023/1024 * लगभग 0 = लगभग .01 बिट है। आपने बहुत कम सीखा है! दूसरा निर्णय ज्यादा बेहतर नहीं है। यही कारण है कि रैखिक खोज इतनी धीमी है। वास्तव में यह सीखने के लिए आवश्यक बिट्स की संख्या में घातीय है।

मान लीजिए कि आप अनुक्रमण कर रहे हैं। मान लीजिए कि तालिका बहुत सारे डिब्बे में पूर्व-क्रमबद्ध है, और आप तालिका प्रविष्टि पर सीधे इंडेक्स करने के लिए कुंजी में से कुछ बिट्स का उपयोग करते हैं। यदि 1024 डिब्बे हैं, तो सभी 1024 संभावित परिणामों के लिए एंट्रॉपी 1/1024 * लॉग (1024) + 1/1024 * लॉग (1024) + ... है। यह 1/1024 * 10 गुना 1024 परिणाम, या उस इंडेक्सिंग ऑपरेशन के लिए 10 बिट्स एंट्रॉपी है। यही कारण है कि अनुक्रमण अनुक्रमण तेजी से है।

अब सॉर्टिंग के बारे में सोचो। आपके पास एन आइटम हैं, और आपके पास एक सूची है। प्रत्येक आइटम के लिए, आपको यह पता लगाना होगा कि आइटम कहां जाता है, और फिर इसे सूची में जोड़ें। तो सॉर्टिंग अंतर्निहित खोज के चरणों की संख्या लगभग N गुना लेता है।

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

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


हमें शुरू से करना चाहिए।

सबसे पहले, सिद्धांत को स्वीकार करें कि डेटा पर कुछ सरल संचालन O(1) समय में किया जा सकता है, यानी, समय के साथ इनपुट के आकार से स्वतंत्र है। सी में इन आदिम संचालन शामिल हैं

  1. अंकगणितीय परिचालन (जैसे + या%)।
  2. तार्किक परिचालन (उदाहरण के लिए, &&)।
  3. तुलना संचालन (उदाहरण के लिए, <=)।
  4. स्ट्रक्चर एक्सेसिंग ऑपरेशंस (उदाहरण के लिए ए [i], या पॉइंटर फोल-डाउनिंग -> ऑपरेटर के साथ सरणी-इंडेक्सिंग)।
  5. सरल असाइनमेंट जैसे वैरिएबल में वैल्यू कॉपी करना।
  6. पुस्तकालय कार्यों के लिए कॉल (उदाहरण के लिए, scanf, printf)।

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

  1. असाइनमेंट स्टेटमेंट्स जिनमें उनके अभिव्यक्तियों में फ़ंक्शन कॉल शामिल नहीं हैं।
  2. बयान पढ़ें।
  3. ऐसे बयान लिखें जिन्हें तर्कों का मूल्यांकन करने के लिए फ़ंक्शन कॉल की आवश्यकता नहीं है।
  4. कूद विवरण, ब्रेक, जारी, गोटो, और वापसी अभिव्यक्ति, जहां अभिव्यक्ति में फ़ंक्शन कॉल नहीं होता है।

सी में, कई फॉर-लूप का गठन कुछ मानों के लिए इंडेक्स वैरिएबल को प्रारंभ करके और उस चर को लूप के चारों ओर 1 बार बढ़ाकर बढ़ाया जाता है। फॉर-लूप समाप्त होता है जब सूचकांक कुछ सीमा तक पहुंच जाता है। उदाहरण के लिए, फॉर-लूप

for (i = 0; i < n-1; i++) 
{
    small = i;
    for (j = i+1; j < n; j++)
        if (A[j] < A[small])
            small = j;
    temp = A[small];
    A[small] = A[i];
    A[i] = temp;
}

सूचकांक चर का उपयोग करता है i। यह लूप के चारों ओर प्रत्येक बार 1 से बढ़ता है, और जब मैं एन -1 तक पहुंचता हूं तो पुनरावृत्ति बंद हो जाती है।

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

उदाहरण के लिए, फॉर-लूप पुनरावृत्त करता है ((n − 1) − 0)/1 = n − 1 times , चूंकि 0 का प्रारंभिक मान i, n-1 है जो उच्चतम मान है (यानी, जब मैं पहुंचता हूं एन -1, लूप बंद हो जाता है और i = n-1 के साथ कोई पुनरावृत्ति नहीं होती है), और 1 लूप के प्रत्येक पुनरावृत्ति पर मुझे जोड़ा जाता है।

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

अब इस उदाहरण पर विचार करें:

(1) for (j = 0; j < n; j++)
(2)   A[i][j] = 0;

हम जानते हैं कि रेखा (1) O(1) समय लेती है। जाहिर है, हम लूप एन बार के चारों ओर जाते हैं, क्योंकि हम पंक्ति (1) पर पाए गए ऊपरी सीमा से निचली सीमा को घटाकर और फिर जोड़ना निर्धारित कर सकते हैं 1. चूंकि शरीर, रेखा (2), ओ (1) समय लेता है, हम जे को बढ़ाने के लिए समय और एन के साथ जे की तुलना करने के लिए समय की उपेक्षा कर सकते हैं, जिनमें से दोनों ओ (1) भी हैं। इस प्रकार, लाइनों का चलने का समय (1) और (2) एन और ओ (1) का उत्पाद है , जो O(n)

इसी तरह, हम बाहरी लूप के चलने वाले समय को बाध्य कर सकते हैं जिसमें लाइन (2) से (4), जो है

(2) for (i = 0; i < n; i++)
(3)     for (j = 0; j < n; j++)
(4)         A[i][j] = 0;

हमने पहले ही स्थापित कर लिया है कि लाइनों (3) और (4) के लूप ओ (एन) समय लेता है। इस प्रकार, हम ओ (1) समय को बढ़ाने के लिए उपेक्षा कर सकते हैं और यह जांचने के लिए कि क्या मैं प्रत्येक पुनरावृत्ति में <n हूं, यह निष्कर्ष निकाला है कि बाहरी लूप के प्रत्येक पुनरावृत्ति ओ (एन) समय लेता है।

बाहरी लूप का प्रारंभिक I = 0 और स्थिति के (एन + 1) सेंट टेस्ट I <n इसी प्रकार ओ (1) समय लेते हैं और इसे उपेक्षित किया जा सकता है। अंत में, हम देखते हैं कि हम बाहरी लूप एन बार के चारों ओर जाते हैं, प्रत्येक पुनरावृत्ति के लिए ओ (एन) समय लेते हैं, कुल O(n^2) चलने का समय देते हैं।

एक और व्यावहारिक उदाहरण।


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

साथ ही मैं यह भी जोड़ना चाहता हूं कि रिकर्सिव फ़ंक्शंस के लिए यह कैसे किया जाता है:

मान लें कि हमारे पास एक फ़ंक्शन है ( स्कीम कोड ):

(define (fac n)
    (if (= n 0)
        1
            (* n (fac (- n 1)))))

जो क्रमशः दिए गए नंबर के फैक्टोरियल की गणना करता है।

पहला कदम केवल इस मामले में फ़ंक्शन के शरीर के प्रदर्शन की विशेषता को निर्धारित करने और निर्धारित करने के लिए है , शरीर में कुछ विशेष नहीं किया जाता है, केवल एक गुणा (या मान 1 की वापसी)।

तो शरीर के लिए प्रदर्शन है: ओ (1) (स्थिर)।

इसके बाद रिकर्सिव कॉल की संख्या के लिए इसे आजमाएं और निर्धारित करें। इस मामले में हमारे पास एन -1 रिकर्सिव कॉल हैं।

तो रिकर्सिव कॉल के लिए प्रदर्शन यह है: ओ (एन -1) (ऑर्डर एन है, क्योंकि हम महत्वहीन हिस्सों को फेंक देते हैं)।

फिर उन दोनों को एक साथ रखें और फिर आपके पास पूरे रिकर्सिव फ़ंक्शन के लिए प्रदर्शन होगा:

1 * (एन -1) = ओ (एन)

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


एल्गोरिदम / डेटा संरचनाओं के साथ परिचितता मैं पुनरावृत्ति घोंसले के उपयोग और / या त्वरित नज़र विश्लेषण। कठिनाई तब होती है जब आप लाइब्रेरी फ़ंक्शन को कॉल करते हैं, संभवतः कई बार - आप अक्सर इस बात से अनिश्चित हो सकते हैं कि आप कभी-कभी फ़ंक्शन को अनावश्यक रूप से कॉल कर रहे हैं या वे किस कार्यान्वयन का उपयोग कर रहे हैं। हो सकता है कि पुस्तकालय कार्यों में जटिलता / दक्षता उपाय हो, चाहे वह बिग ओ या कुछ अन्य मीट्रिक हो, जो दस्तावेज़ीकरण या यहां तक ​​कि IntelliSense भी उपलब्ध है।


बिग ओ एक एल्गोरिदम की समय जटिलता के लिए ऊपरी बाउंड देता है। यह आमतौर पर प्रोसेसिंग डेटा सेट (सूचियों) के संयोजन के साथ प्रयोग किया जाता है लेकिन इसका इस्तेमाल कहीं और किया जा सकता है।

सी कोड में इसका उपयोग कैसे किया जाता है इसके कुछ उदाहरण।

मान लें कि हमारे पास एन तत्वों की एक सरणी है

int array[n];

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

x = array[0];

अगर हम सूची में कोई संख्या खोजना चाहते हैं:

for(int i = 0; i < n; i++){
    if(array[i] == numToFind){ return i; }
}

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

जब हम नेस्टेड लूप प्राप्त करते हैं:

for(int i = 0; i < n; i++){
    for(int j = i; j < n; j++){
        array[j] += 2;
    }
}

यह ओ (एन ^ 2) है क्योंकि बाहरी लूप (ओ (एन) के प्रत्येक पास के लिए हमें फिर से पूरी सूची में जाना होगा ताकि एन हमें गुणा के साथ गुणा कर सके।

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


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

एक बहुत ही सरल उदाहरण के रूप में आप .NET ढांचे की सूची प्रकार की गति पर एक सैनिटी जांच करना चाहते थे। आप निम्न की तरह कुछ लिख सकते हैं, फिर यह सुनिश्चित करने के लिए Excel में परिणामों का विश्लेषण करें कि वे एन * लॉग (एन) वक्र से अधिक नहीं हैं।

इस उदाहरण में मैं तुलना की संख्या को मापता हूं, लेकिन प्रत्येक नमूना आकार के लिए आवश्यक वास्तविक समय की जांच करना भी समझदार है। हालांकि, आपको और भी सावधान रहना चाहिए कि आप केवल एल्गोरिदम को माप रहे हैं और आपके परीक्षण आधारभूत संरचना से कलाकृतियों को शामिल नहीं कर रहे हैं।

int nCmp = 0;
System.Random rnd = new System.Random();

// measure the time required to sort a list of n integers
void DoTest(int n)
{
   List<int> lst = new List<int>(n);
   for( int i=0; i<n; i++ )
      lst[i] = rnd.Next(0,1000);

   // as we sort, keep track of the number of comparisons performed!
   nCmp = 0;
   lst.Sort( delegate( int a, int b ) { nCmp++; return (a<b)?-1:((a>b)?1:0)); }

   System.Console.Writeline( "{0},{1}", n, nCmp );
}


// Perform measurement for a variety of sample sizes.
// It would be prudent to check multiple random samples of each size, but this is OK for a quick sanity check
for( int n = 0; n<1000; n++ )
   DoTest(n);

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

मूल बातें

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

  • 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)... और टाइप करना आसान है। ;-)





algorithm optimization complexity-theory big-o performance