लूप

Question

के लिए डबल की जटिलता मैं बिग ओ नोटेशन का उपयोग करके लूप की जटिलता को समझने की कोशिश कर रहा हूं। मैंने इसे अपने अन्य वर्गों में पहले किया है, लेकिन यह दूसरों की तुलना में अधिक कठोर है क्योंकि यह वास्तविक एल्गोरिदम पर है। कोड इस प्रकार है:

for(cnt = 0, i=1; i<=n; i++) //for any size n 
{ 
    for(j = 1; j <= i; j++) 
    { 
     cnt++; 
    } 
} 

और

for(cnt = 0, i=1; i<=n; i*=2) //for any size n 
{ 
    for(j = 1; j <= i; j++) 
    { 
     cnt++; 
    } 
} 

मैं आ चुके हैं कि पहली पाश हे (एन) जटिलता का है, क्योंकि यह सूची n समय से गुजर रही है। दूसरे लूप के लिए मैं थोड़ा खो गया हूँ। मेरा मानना ​​है कि यह प्रत्येक एन के लिए लूप के माध्यम से जा रहा है जिसे परीक्षण किया जाता है। मैंने (गलत तरीके से) माना है कि इसका मतलब यह है कि लूप ओ (एन * i) प्रत्येक बार मूल्यांकन के लिए होता है। क्या ऐसी कोई चीज है जो मैं अपनी धारणा में लापता हूं। मुझे पता है कि cnt ++ निरंतर समय है।

विश्लेषण में सहायता के लिए धन्यवाद। प्रत्येक पाश अपनी जगह पर है, वे एक साथ नहीं हैं।

Answer 1

पहले उदाहरण के बाहरी पाश n बार निष्पादित करता है। बाहरी पाश के प्रत्येक पुनरावृत्ति के लिए, आंतरिक पाश को i बार निष्पादित किया जाता है, इसलिए समग्र जटिलता को निम्नानुसार गणना की जा सकती है: पहले पुनरावृत्ति के लिए दो और दूसरा पुनरावृत्ति के लिए दो और तीसरे पुनरावृत्ति के लिए तीन और इसी तरह, n के लिए n -थ पुनरावृत्ति।

1+2+3+4+5+...+n = (n*(n-1))/2 --> O(n^2) 

दूसरे उदाहरण जटिल काम है: i युगल हर यात्रा के बाद से, बाहरी पाश केवल Log2(n) बार निष्पादित करता है। यह मानते हुए कि n2 की एक शक्ति है, भीतरी पाश के लिए कुल

1+2+4+8+16+...+n 

जो जटिलता O(n) के लिए 2^Log2(n)-1 = n-1 है।

n के लिए कि दो की शक्तियों पुनरावृत्तियों की सही संख्या (2^(Log2(n)+1))-1 है नहीं कर रहे हैं, जो अभी भी O(n) है:

1  -> 1 
2..3 -> 3 
4..7 -> 7 
8..15 -> 15 
16..31 -> 31 
32..63 -> 63 

और इतने पर।

Answer 2

उम्मीद है कि इस होमवर्क नहीं है, लेकिन मैं देख पा रहे हैं कि आप कम से कम यहाँ एक प्रयास किया है, तो यहां इस पर मेरी ले रहा है:

cnt वृद्धि n * है (n + 1)/2 बार है, जो दोनों loops ओ (एन^2) का पूरा सेट बनाता है। दूसरा लूप औसत पर ओ (एन/2) है, जो ओ (एन) है।

Answer 3

पहला उदाहरण ओ (एन^2) और What is the Big-O of a nested loop, where number of iterations in the inner loop is determined by the current iteration of the outer loop? प्रश्न होगा जो उत्तर देता है कि कुंजी कहां है कि आंतरिक लूप की संख्या राउंड पर निर्भर है।

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