मुझे कोड कोड

Question

का बिग-ओह खोजने का तरीका समझने में मदद की ज़रूरत है, मेरा कंप्यूटर साइंस II फ़ाइनल कल है, और मुझे कोड की सेगमेंट के लिए बिग-ओह को कैसे ढूंढें, यह समझने में कुछ मदद चाहिए। मैंने इंटरनेट की खोज की है और मुझे यह समझने में सक्षम नहीं है कि मुझे इसे कैसे समझना है।

for(int pass = 1; i <= n; pass++) 
{ 
    for(int index = 0; index < n; index++) 
     for(int count = 1; count < n; count++) 
     { 
      //O(1) things here. 
     } 
    } 
} 

हम एल्गोरिथ्म के आदेश (बिग-ओह) को खोजने के लिए अपेक्षा की जाती है:

यहाँ अंतिम हमारे नमूना से एक समस्या है।

मुझे लगता है कि हे कि यह होगा (एन^3), और यहाँ कैसे मुझे लगता है कि इस निष्कर्ष

for(int pass = 1; i <= n; pass++) // Evaluates n times 
{ 
    for(int index = 0; index < n; index++) // Evaluates n * (n+1) times 
     for(int count = 1; count < n; count++) // Evaluates n * n * (n) times 
     { 
      //O(1) things here. 
     } 
    } 
} 
// T(n) = (n) + (n^2 + n) + n^3 
// T(n) = n^3 + n^2 + 2n 
// T(n) <= c*f(x) 
// n^3 + n^2 + 2n <= c * (n^3) 
// O(n) = n^3 

मैं सिर्फ यकीन है कि अगर मैं इसे सही ढंग से कर रहा हूँ नहीं कर रहा हूँ के लिए आया था है। क्या कोई इस तरह के कोड का मूल्यांकन कैसे कर सकता है और/या मेरे उत्तर की पुष्टि कर सकता है?

Answer 1

हां, यह O(n^3) है। हालांकि:

for(int pass = 1; pass <= n; pass++) // Evaluates n times 
{     //^^i should be pass 

    for(int index = 0; index < n; index++) //Evaluates n times 
     for(int count = 1; count < n; count++) // Evaluates n-1 times 
     { 
      //O(1) things here. 
     } 
    } 
} 

जब से तुम छोरों के लिए नेस्टेड के तीन परत है, नेस्टेड लूप n *n * (n-1) बार, हर आपरेशन मूल्यांकन किया जाएगा पाश के लिए सबसे भीतरी अंदर लेता हे (1) समय है, तो कुल में आप n^3 - n^2 निरंतर है संचालन, जो विकास के क्रम में O(n^3) है।

कैसे बिग ओ अंकन में वृद्धि के आदेश को मापने के लिए का एक अच्छा सारांश यहां पाया जा सकता:

Big O Notation MIT

ऊपर फ़ाइल से भाग का हवाला देते हुए:

नेस्टेड लूप

for I in 1 .. N loop 
    for J in 1 .. M loop 
     sequence of statements 
    end loop; 
end loop; 

बाहरी पाश एन बार निष्पादित करता है। जब भी बाहरी पाश निष्पादित होता है, आंतरिक लूप एम बार निष्पादित करता है। नतीजतन, आंतरिक पाश में बयान कुल एन * एम बार निष्पादित करते हैं। इस प्रकार, जटिलता ओ (एन * एम) है। एक सामान्य विशेष मामले में जहां आंतरिक लूप की रोकथाम स्थिति J <N J <M (यानी, आंतरिक पाश भी एन बार निष्पादित करती है), दो लूपों की कुल जटिलता ओ (एन^2) है।

इसी तरह के तर्क आपके मामले में लागू किया जा सकता है।

Answer 2

आप बिल्कुल सही हैं। यह आपके उदाहरण के लिए ओ (एन^3) है।

कोड के किसी भी सेगमेंट के बिग ओह रनिंग टाइम को खोजने के लिए, आपको इस बारे में सोचना चाहिए कि कोड का टुकड़ा ओ (1) चीजें कितनी बार करता है।

मुझे अपने उदाहरण को आसान बनाने में इस का एक बेहतर विचार देने के लिए करते हैं:

for(int index = 0; index < n; index++) // Evaluates n * (n+1) times 
    for(int count = 1; count < n; count++) // Evaluates n * n * (n) times 
    { 
     //O(1) things here. 
    } 
} 

ऊपर मामले में, भीतरी पाश बाहरी पाश के प्रत्येक रन के लिए एन बार चलाता है। और आपका बाहरी पाश भी एन बार चलाता है। इसका मतलब है कि आप एन चीजें कर रहे हैं, कई बार। इसे बनाना ओ (एन^2)।

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

for(int index = 0; index < n; index++) // Evaluates n * (n+1) times 
    for(int count = 1; count < 2*n; count++) // Runs 2*n times 
    { 
     //O(1) things here. 
    } 
} 

बिग ओह इस कोड के प्रसारण समय भी है O (n^2) के बाद से O (n * (2n)) = O (n^2)

। यह भी देखें: http://ellard.org/dan/www/Q-97/HTML/root/node7.html