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




optimization complexity-theory (16)

आम तौर पर कम उपयोगी, मुझे लगता है, लेकिन पूर्णता के लिए एक बिग ओमेगा think भी है, जो एक एल्गोरिथ्म की जटिलता पर एक निचली-सीमा को परिभाषित करता है, और एक बड़ी थीटा Θ , जो ऊपरी और निचले दोनों को परिभाषित करता है।

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

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

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


एल्गोरिथ्म को उन टुकड़ों में तोड़ें जिनके बारे में आप जानते हैं कि बड़े O संकेतन, और बड़े O ऑपरेटरों के माध्यम से संयोजित होते हैं। केवल यही एक तरीका है जिसके बारे में मुझे पता है।

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


छोटे अनुस्मारक: big O अंकन का उपयोग असममित जटिलता को निरूपित करने के लिए किया जाता है (अर्थात, जब समस्या का आकार अनंत तक बढ़ता है), और यह एक निरंतर छुपाता है।

इसका मतलब यह है कि O (n) और एक O (n 2 ) में एक एल्गोरिथ्म के बीच, सबसे तेज़ हमेशा पहला नहीं होता है (हालाँकि वहाँ हमेशा n का मान होता है जैसे कि> n की समस्याओं के लिए, पहला एल्गोरिथम है सबसे तेज़)।

ध्यान दें कि छिपा हुआ स्थिरांक बहुत कुछ कार्यान्वयन पर निर्भर करता है!

इसके अलावा, कुछ मामलों में, रनटाइम इनपुट के आकार n का एक नियतात्मक कार्य नहीं है। उदाहरण के लिए त्वरित प्रकार का उपयोग करके छंटाई करें: n तत्वों की एक सरणी को सॉर्ट करने के लिए आवश्यक समय एक स्थिर नहीं है, लेकिन सरणी के शुरुआती कॉन्फ़िगरेशन पर निर्भर करता है।

अलग-अलग समय जटिलताएं हैं:

  • सबसे खराब स्थिति (आमतौर पर यह पता लगाने के लिए सबसे सरल, हालांकि हमेशा बहुत सार्थक नहीं)
  • औसत मामला (आमतौर पर यह पता लगाने के लिए बहुत कठिन ...)

  • ...

एक अच्छा परिचय आर। सेडग्विक और पी। फ्लाजोलेट द्वारा एल्गोरिदम के विश्लेषण का एक परिचय है

जैसा कि आप कहते हैं, premature optimisation is the root of all evil , और (यदि संभव हो तो) प्रोफाइल को कोड का अनुकूलन करते समय वास्तव में हमेशा उपयोग किया जाना चाहिए। यह आपके एल्गोरिदम की जटिलता को निर्धारित करने में भी आपकी मदद कर सकता है।


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

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

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

int array[n];

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

x = array[0];

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

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

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

जब हम नेस्टेड छोरों के लिए मिलता है:

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

यह O (n ^ 2) है क्योंकि बाहरी लूप (O (n)) के प्रत्येक पास के लिए हमें फिर से पूरी सूची से गुजरना पड़ता है इसलिए n का गुणा हमें n वर्ग से छोड़ता है।

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


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

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

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

इसलिए हम O (n * log (n)) द्वारा कार्य की मात्रा को बढ़ा सकते हैं।

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

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

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

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

1 + 2 + 3 + ... + n = n (n-1) / 2 = O (n ^ 2)

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


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

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


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

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

एक "कुकबुक" के रूप में, 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 मान लेता है। अब हमें फंक्शन f() की वास्तविक परिभाषा की आवश्यकता है। यह स्रोत कोड से किया जाता है, जिसमें प्रत्येक दिलचस्प रेखा 1 से 4 तक गिने जाती है।

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

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

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

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

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

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

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

वास्तविक बिगओ को प्राप्त करने के लिए हमें फ़ंक्शन के एसिम्प्टोटिक विश्लेषण की आवश्यकता होती है। यह लगभग इस तरह किया जाता है:

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

हमारे f() में दो पद हैं:

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

सभी C स्थिरांक और निरर्थक भागों को दूर करना:

f(N) = 1 + N ^ 1

चूँकि अंतिम शब्द वह है जो बड़ा होता है जब f() अनंत से संपर्क करता है ( limits पर सोचें) यह BigOh तर्क है, और sum() फ़ंक्शन का BigOh है:

O(N)

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

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

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

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

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

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

वाक्य संख्या दो और भी पेचीदा है क्योंकि यह i के मूल्य पर निर्भर करता है। एक नज़र डालें: सूचकांक मैं मान लेता है: 0, 2, 4, 6, 8, ..., 2 * एन, और दूसरे for निष्पादित करने के लिए: एन पहली बार एक, एन - 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 चरण लेता 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 जाएगा, और हम इसके शरीर पर एक निरंतर C निष्पादन जटिलता मान रहे हैं।

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

  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

और BigOh है:

O(N²)

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

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


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

यहाँ कुछ सबसे सामान्य मामले हैं, जिन्हें http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions से उठाया गया है:

O (1) - यदि संख्या समान या विषम है, तो यह निर्धारित करना; निरंतर-आकार लुकअप तालिका या हैश तालिका का उपयोग करना

O (logn) - बाइनरी खोज के साथ सॉर्ट की गई सरणी में एक आइटम ढूँढना

ओ (एन) - एक अनसुलझी सूची में एक आइटम ढूँढना; दो n अंकों की संख्याओं को जोड़ना

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

O (n 3 ) - सरल एल्गोरिथ्म द्वारा दो n × n मैट्रिसेस गुणा करना

O (c n ) - डायनामिक प्रोग्रामिंग का उपयोग करके यात्रा विक्रेता समस्या का (सटीक) समाधान खोजना; यह निर्धारित करना कि दो तार्किक कथन पाशविक बल के समतुल्य हैं

O (n!) - ब्रूट-फोर्स सर्च के माध्यम से ट्रैवलिंग सेल्समैन समस्या का समाधान

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


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

इसके अलावा मैं यह भी जोड़ना चाहूंगा कि यह पुनरावर्ती कार्यों के लिए कैसे किया जाता है:

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

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

जो दिए गए संख्या के भाज्य की गणना करता है।

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

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

अगली कोशिश करें और पुनरावर्ती कॉल की संख्या के लिए इसे निर्धारित करें। इस मामले में हमारे पास n-1 पुनरावर्ती कॉल हैं।

तो पुनरावर्ती कॉल के लिए प्रदर्शन है: O (n-1) (आदेश n है, क्योंकि हम तुच्छ भागों को फेंक देते हैं)।

फिर उन दोनों को एक साथ रखें और आपके पास पूरे पुनरावर्ती कार्य के लिए प्रदर्शन है:

1 * (n-1) = O (n)

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


बड़ा सवाल!

डिस्क्लेमर: इस उत्तर में गलत कथन हैं, नीचे दी गई टिप्पणियों को देखें।

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

बिग ओ की एक सुंदर औपचारिक परिभाषा के लिए इस साइट को https://xlinux.nist.gov/dads/HTML/bigOnotation.html : https://xlinux.nist.gov/dads/HTML/bigOnotation.html

f (n) = O (g (n)) का अर्थ है सकारात्मक स्थिरांक c और k, जैसे कि 0 ≤ f (n) n cg (n) सभी n। k के लिए। फ़ंक्शन च के लिए c और k का मान निश्चित होना चाहिए और n पर निर्भर नहीं होना चाहिए।

ठीक है, तो अब हम "बेस्ट-केस" और "सबसे खराब-केस" जटिलताओं से क्या मतलब है?

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

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

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


मैं नहीं जानता कि इसे कैसे हल किया जाए, लेकिन सबसे पहली बात यह है कि हम किए गए कार्यों की संख्या में कुछ पैटर्न के लिए एल्गोरिथ्म का नमूना लेते हैं, कहते हैं 4n ^ 2 + 2n + 1 हमारे पास 2 नियम हैं:

  1. यदि हमारे पास शब्द हैं, तो सबसे बड़ी विकास दर के साथ शब्द रखा गया है, अन्य शर्तों के साथ छोड़ दिया गया है।
  2. यदि हमारे पास कई कारकों का एक उत्पाद है तो स्थिर कारक छोड़ दिए जाते हैं।

यदि हम f (x) को सरल बनाते हैं, जहाँ f (x) किए गए कार्यों की संख्या का सूत्र है, (4n ^ 2 + 2n + 1 ऊपर बताया गया है), तो हम इसमें बड़े-O मान [O (n ^ 2) प्राप्त करते हैं। मामला]। लेकिन इस कार्यक्रम में लैग्रेग प्रक्षेप के लिए जिम्मेदार होगा, जिसे लागू करना कठिन हो सकता है। और क्या होगा यदि वास्तविक बड़ा-ओ मान O (2 ^ n) था, और हमारे पास O (x ^ n) जैसा कुछ हो सकता है, इसलिए यह एल्गोरिथम शायद प्रोग्राम करने योग्य नहीं होगा। लेकिन अगर कोई मुझे गलत साबित करता है, तो मुझे कोड दें। । । ।


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

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


अंतरिक्ष जटिलताओं के लिए अनुमति देना भी न भूलें जो कि सीमित स्मृति संसाधन होने पर भी चिंता का कारण हो सकते हैं। इसलिए उदाहरण के लिए आप किसी को एक निरंतर स्थान एल्गोरिथ्म चाहने वाले सुन सकते हैं जो मूल रूप से कहने का एक तरीका है कि एल्गोरिथ्म द्वारा ली गई अंतरिक्ष की मात्रा कोड के अंदर किसी भी कारक पर निर्भर नहीं करती है।

कभी-कभी जटिलता यह कह सकती है कि कितनी बार कुछ कहा जाता है, कितनी बार एक लूप निष्पादित किया जाता है, कितनी बार मेमोरी आवंटित की जाती है, और इसी तरह इस प्रश्न का उत्तर देने के लिए एक और हिस्सा है।

अंत में, बिग ओ का उपयोग सबसे खराब स्थिति, सर्वोत्तम मामले और परिशोधन के मामलों के लिए किया जा सकता है, जहां आमतौर पर यह सबसे खराब मामला है जिसका उपयोग यह बताने के लिए किया जाता है कि एल्गोरिथ्म कितना बुरा हो सकता है।


कोड ए के लिए, बाहरी लूप n+1समय के लिए निष्पादित करेगा , '1' समय का अर्थ है वह प्रक्रिया जो जांचती है कि क्या मैं अभी भी आवश्यकता को पूरा करता हूं। और भीतर का पाश nबार, n-2बार चलता है .... इस प्रकार 0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²),।

कोड बी के लिए, हालांकि आंतरिक लूप चरण में नहीं आएगा और फू को निष्पादित करेगा (), आंतरिक लूप को निष्पादित किया जाएगा एन समय के लिए बाहरी लूप निष्पादन समय पर निर्भर करता है, जो कि ओ (एन) है।


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

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

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

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);




performance