algorithm - एल्गोरिदम की समय जटिलता कैसे प्राप्त करें




time-complexity complexity-theory (7)

प्रश्न

एल्गोरिदम की समय जटिलता कैसे प्राप्त करें?

एसओ पर एक प्रश्न पोस्ट करने से पहले मैंने क्या किया है?

मैं this और कई अन्य लिंक से गुजर चुका हूं

लेकिन समय जटिलता की गणना करने के लिए मैं स्पष्ट और सीधे आगे स्पष्टीकरण नहीं ढूंढ पाया।

मुझे क्या पता ?

नीचे दिए गए कोड के रूप में एक कोड के लिए कहें:

char h = 'y'; // This will be executed 1 time
int abc = 0; // This will be executed 1 time

नीचे दिए गए की तरह एक लूप के लिए कहें:

for (int i = 0; i < N; i++) {        
    Console.Write('Hello World !');
}

int i = 0; यह केवल एक बार निष्पादित किया जाएगा। समय वास्तव में i=0 गणना की जाती है और घोषणा नहीं होती है।

मैं <एन; इसे एन + 1 बार निष्पादित किया जाएगा

मैं ++; यह एन बार निष्पादित किया जाएगा

तो इस लूप द्वारा आवश्यक संचालन की संख्या हैं

{1+ (एन + 1) + एन} = 2 एन + 2

नोट: यह अभी भी गलत हो सकता है, क्योंकि मुझे समय जटिलता की गणना करने पर मेरी समझ के बारे में विश्वास नहीं है

मै क्या जानना चाहता हूँ ?

ठीक है, इसलिए मुझे लगता है कि ये छोटी बुनियादी गणना मुझे पता है, लेकिन ज्यादातर मामलों में मैंने समय जटिलता देखी है

ओ (एन), ओ (एन 2), ओ (लॉग एन), ओ (एन!) .... और कई other ,

क्या कोई मुझे समझने में मदद कर सकता है कि कोई एल्गोरिदम की समय जटिलता की गणना कैसे करता है? मुझे यकीन है कि मेरे जैसे बहुत सारे नए लोग इसे जानना चाहते हैं।


एल्गोरिदम की समय जटिलता कैसे प्राप्त करें

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

उदाहरण के लिए, देखते हैं कि हम 2N + 2 O(N) रूप में इसका वर्णन करने के लिए 2N + 2 मशीन निर्देशों को कैसे सरल बनाते हैं।

हम दो 2 एस क्यों हटाते हैं?

हम एल्गोरिदम के प्रदर्शन में रूचि रखते हैं क्योंकि एन बड़ा हो जाता है।

दो शर्तों 2 एन और 2 पर विचार करें।

इन दो शर्तों का सापेक्ष प्रभाव क्या है क्योंकि एन बड़ा हो जाता है? मान लीजिए एन एक लाख है।

फिर पहला शब्द 2 मिलियन है और दूसरा शब्द केवल 2 है।

इस कारण से, हम बड़े एन के लिए सबसे बड़ी शर्तों को छोड़कर सभी को छोड़ देते हैं।

तो, अब हम 2N + 2 से 2N + 2 तक चले गए हैं।

परंपरागत रूप से, हम केवल स्थिर कारकों तक प्रदर्शन में रूचि रखते हैं

इसका मतलब यह है कि जब हम बड़े होते हैं तो प्रदर्शन में अंतर के कुछ निरंतर एकाधिक होते हैं तो हम वास्तव में परवाह नहीं करते हैं। वैसे भी 2 एन की इकाई पहले स्थान पर अच्छी तरह से परिभाषित नहीं है। इसलिए हम सबसे सरल अभिव्यक्ति प्राप्त करने के लिए निरंतर कारक से गुणा या विभाजित कर सकते हैं।

तो 2N N सिर्फ N बन जाता है।


उदाहरण के साथ समय जटिलता

1 - मूल संचालन (अंकगणित, तुलना, सरणी के तत्वों का उपयोग, असाइनमेंट): चलने का समय हमेशा स्थिर रहता है ओ (1)

उदाहरण :

read(x)                               // O(1)
a = 10;                               // O(1)
a = 1.000.000.000.000.000.000         // O(1)

2 - यदि फिर और कथन: केवल दो या अधिक संभावित बयानों से अधिकतम चलने का समय लेना।

उदाहरण:

age = read(x)                               // (1+1) = 2
if age < 17 then begin                      // 1
      status = "Not allowed!";              // 1
end else begin
      status = "Welcome! Please come in";   // 1
      visitors = visitors + 1;              // 1+1 = 2
end;

तो, उपरोक्त छद्म कोड की जटिलता टी (एन) = 2 + 1 + अधिकतम (1, 1 + 2) = 6. है। इस प्रकार, इसका बड़ा ओह अभी भी निरंतर टी (एन) = ओ (1) है।

3 - लूपिंग (के लिए, जबकि, दोहराएं): इस कथन के लिए चलने का समय उस लूपिंग के अंदर संचालन की संख्या से गुणा करने वाली लूपिंग की संख्या है।

उदाहरण:

total = 0;                                  // 1
for i = 1 to n do begin                     // (1+1)*n = 2n
      total = total + i;                    // (1+1)*n = 2n
end;
writeln(total);                             // 1

तो, इसकी जटिलता टी (एन) = 1 + 4 एन + 1 = 4 एन + 2. है, इस प्रकार, टी (एन) = ओ (एन)।

4 - नेस्टेड लूप (लूपिंग के अंदर लूपिंग): चूंकि मुख्य लूपिंग के अंदर कम से कम एक लूपिंग है, इस कथन का चलने वाला समय O (n ^ 2) या O (n ^ 3) का उपयोग करता है।

उदाहरण:

for i = 1 to n do begin                     // (1+1)*n  = 2n
   for j = 1 to n do begin                  // (1+1)n*n = 2n^2
       x = x + 1;                           // (1+1)n*n = 2n^2
       print(x);                            // (n*n)    = n^2
   end;
end;

सामान्य चलने का समय

एल्गोरिदम का विश्लेषण करते समय कुछ सामान्य चलने वाले समय होते हैं:

  1. ओ (1) - निरंतर समय निरंतर समय का मतलब है कि चलने का समय स्थिर है, यह इनपुट आकार से प्रभावित नहीं है

  2. ओ (एन) - रैखिक समय जब एक एल्गोरिदम एन इनपुट आकार स्वीकार करता है, तो यह एन संचालन भी करेगा।

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

  4. ओ (एन लॉग एन) - लिनियरिदमिक टाइम यह चलने वाला समय अक्सर "एल्गोरिदम को विभाजित और जीतने" में पाया जाता है जो समस्या को उप-समस्याओं में दोबारा विभाजित करता है और फिर उन्हें समय में विलय करता है। उदाहरण: क्रमबद्ध एल्गोरिदम मर्ज करें।

  5. ओ (एन 2 ) - क्वाड्रैटिक टाइम लुक बबल सॉर्ट एल्गोरिदम!

  6. ओ (एन 3 ) - घन समय यह ओ (एन 2 ) के साथ एक ही सिद्धांत है।

  7. ओ (2 एन ) - घातीय समय यह बहुत धीमा है क्योंकि इनपुट बड़ा हो जाता है, अगर एन = 1000.000, टी (एन) 21000.000 होगा। ब्रूट फोर्स एल्गोरिदम में यह चलने का समय है।

  8. हे (एन!) - सख्त फैक्टोरियल टाइम !!! उदाहरण: ट्रैवल सेल्समैन समस्या (टीएसपी)

इस लेख से लिया गया। बहुत अच्छी तरह से समझाया जाना चाहिए पढ़ना चाहिए।


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

For i= 1 to n;
  j= 0;
while(j<=n);
  j=j+1;

यहां आंतरिक लूप के लिए निष्पादन की कुल संख्या एन + 1 है और बाहरी लूप के लिए निष्पादन की कुल संख्या एन (एन + 1) / 2 है, इसलिए पूरे एल्गोरिदम के लिए निष्पादन की कुल संख्या एन + 1 + एन (एन + 1/2) है ) = (एन ^ 2 + 3 एन) / 2। यहां एन ^ 2 हावी शब्द है इसलिए इस एल्गोरिदम के लिए समय जटिलता ओ (एन ^ 2) है


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

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

आइए देखें कि एल्गोरिदम की समय जटिलता के लिए क्या संभावनाएं हैं, आप ऊपर वर्णित विकास के क्रम को देख सकते हैं:

  • निरंतर समय में वृद्धि 1 का क्रम है, उदाहरण के लिए: a = b + c

  • लॉगरिदमिक समय में LogN के विकास का क्रम होता है, यह आमतौर पर तब होता है जब आप आधा (बाइनरी खोज, पेड़, यहां तक ​​कि लूप) में कुछ विभाजित कर रहे हैं, या किसी भी तरह से गुणा कर रहे हैं।

  • रैखिक , विकास का क्रम N , उदाहरण के लिए

    int p = 0;
    for (int i = 1; i < N; i++)
      p = p + 2;
    
  • n*logN , विकास का क्रम n*logN , आमतौर पर विभाजित होता है और एल्गोरिदम n*logN है।

  • घन , N^3 के विकास का क्रम, क्लासिक उदाहरण एक ट्रिपल लूप है जहां आप सभी तीनों की जांच करते हैं:

    int x = 0;
    for (int i = 0; i < N; i++)
       for (int j = 0; j < N; j++)
          for (int k = 0; k < N; k++)
              x = x + 2
    
  • घातीय , विकास 2^N का क्रम आमतौर पर तब होता है जब आप संपूर्ण खोज करते हैं, उदाहरण के लिए कुछ सेट के सबसेट जांचें।


यह एक उत्कृष्ट लेख है: http://www.daniweb.com/software-development/computer-science/threads/13488/time-complexity-of-algorithm

नीचे दिया गया उत्तर ऊपर से कॉपी किया गया है (यदि उत्कृष्ट लिंक बस्ट जाता है)

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

statement;

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

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

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

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

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

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

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

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

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

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

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


यहां से लिया गया - एक एल्गोरिदम की समय जटिलता का परिचय

1। परिचय

कंप्यूटर विज्ञान में, एल्गोरिदम की समय जटिलता इनपुट का प्रतिनिधित्व करने वाली स्ट्रिंग की लंबाई के फ़ंक्शन के रूप में चलाने के लिए एल्गोरिदम द्वारा उठाए गए समय की मात्रा को प्रमाणित करती है।

2. बिग ओ नोटेशन

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

उदाहरण के लिए, यदि आकार एन के सभी इनपुट पर एल्गोरिदम द्वारा आवश्यक समय अधिकतम 5 एन 3 + 3 एन पर है, तो एसिम्प्टोटिक समय जटिलता ओ (एन 3 ) है। उस पर और अधिक।

कुछ और उदाहरण:

  • 1 = ओ (एन)
  • एन = ओ (एन 2 )
  • लॉग (एन) = ओ (एन)
  • 2 एन + 1 = ओ (एन)

3. ओ (1) लगातार समय:

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

उदाहरण:

  • सरणी: किसी भी तत्व का उपयोग
  • निश्चित आकार का ढेर: पुश और पॉप विधियां
  • निश्चित आकार कतार: enqueue और dequeue विधियों

4. ओ (एन) रैखिक समय

एक एल्गोरिदम को रैखिक समय में चलाने के लिए कहा जाता है यदि इसका समय निष्पादन इनपुट आकार के लिए सीधे आनुपातिक होता है, यानी इनपुट आकार बढ़ने के साथ समय रेखा बढ़ता है।

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

int find = 66;
var numbers = new int[] { 33, 435, 36, 37, 43, 45, 66, 656, 2232 };
for (int i = 0; i < numbers.Length - 1; i++)
{
    if(find == numbers[i])
    {
        return;
    }
}

और ज्यादा उदाहरण:

  • ऐरे: रैखिक खोज, ट्रैवर्सिंग, न्यूनतम खोजें आदि
  • ArrayList: विधि शामिल है
  • कतार: विधि शामिल है

5. ओ (लॉग एन) लॉगरिदमिक समय:

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

उदाहरण: बाइनरी खोज

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

6. ओ (एन 2) वर्गिक समय

एक एल्गोरिदम को चौकोर समय में चलाने के लिए कहा जाता है यदि इसका समय निष्पादन इनपुट आकार के वर्ग के समान होता है।

उदाहरण:

7. कुछ उपयोगी लिंक


हालांकि इस सवाल के लिए कुछ अच्छे जवाब हैं। मैं loop कई उदाहरणों के साथ यहां एक और जवाब देना चाहता हूं।

  • ओ (एन) : लूप की समय जटिलता को ओ (एन) के रूप में माना जाता है यदि लूप वैरिएबल निरंतर मात्रा में वृद्धि / कमी हो जाती है। उदाहरण के लिए निम्नलिखित कार्यों में ओ (एन) समय जटिलता है।

    // Here c is a positive integer constant   
    for (int i = 1; i <= n; i += c) {  
        // some O(1) expressions
    }
    
    for (int i = n; i > 0; i -= c) {
        // some O(1) expressions
    }
    
  • ओ (एन ^ सी) : नेस्टेड लूप की समय जटिलता अंतर्निहित कथन निष्पादित होने की संख्या के बराबर होती है। उदाहरण के लिए निम्नलिखित नमूना loops ओ (एन ^ 2) समय जटिलता है

    for (int i = 1; i <=n; i += c) {
       for (int j = 1; j <=n; j += c) {
          // some O(1) expressions
       }
    }
    
    for (int i = n; i > 0; i += c) {
       for (int j = i+1; j <=n; j += c) {
          // some O(1) expressions
    }
    

    उदाहरण के लिए चयन क्रम और सम्मिलन क्रम में ओ (एन ^ 2) समय जटिलता है।

  • ओ (लॉगन) लूप की समय जटिलता को ओ (लॉगन) के रूप में माना जाता है यदि लूप चर को निरंतर राशि से विभाजित / गुणा किया जाता है।

    for (int i = 1; i <=n; i *= c) {
       // some O(1) expressions
    }
    for (int i = n; i > 0; i /= c) {
       // some O(1) expressions
    }
    

    उदाहरण के लिए बाइनरी सर्च में ओ (लॉगन) समय जटिलता है।

  • ओ (लॉगलोग्न) लूप की समय जटिलता को ओ (लॉगलोग्न) के रूप में माना जाता है यदि लूप वैरिएबल को निरंतर मात्रा में तेजी से बढ़ाया जाता है / बढ़ाया जाता है।

    // Here c is a constant greater than 1   
    for (int i = 2; i <=n; i = pow(i, c)) { 
       // some O(1) expressions
    }
    //Here fun is sqrt or cuberoot or any other constant root
    for (int i = n; i > 0; i = fun(i)) { 
       // some O(1) expressions
    }
    

समय जटिलता विश्लेषण का एक उदाहरण

int fun(int n)
{    
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < n; j += i)
        {
            // Some O(1) task
        }
    }    
}

विश्लेषण :

For i = 1, the inner loop is executed n times. For i = 2, the inner loop is executed approximately n/2 times. For i = 3, the inner loop is executed approximately n/3 times. For i = 4, the inner loop is executed approximately n/4 times. ……………………………………………………. For i = n, the inner loop is executed approximately n/n times.

तो उपर्युक्त एल्गोरिदम की कुल समय जटिलता (n + n/2 + n/3 + … + n/n) , जो n * (1/1 + 1/2 + 1/3 + … + 1/n)

श्रृंखला के बारे में महत्वपूर्ण बात (1/1 + 1/2 + 1/3 + … + 1/n) ओ (लॉगन) के बराबर है। तो उपरोक्त कोड की समय जटिलता ओ (nLogn) है

रेफरी: 1 2 3





complexity-theory