void bar(int N){
int c=0;
for (int i=0; i<N*N; i++)
for (int j= i; j< N; j++)
c++;
}
बाहरी (और भीतरी) ऊपर अतीत एन इसका मतलब यह होगा मिल कभी नहीं छोरों बिग ओ एन * एन (एन बाहरी और भीतरी के लिए एन/2 के लिए) क्या है?बिग ओ - नेस्टेड लूप
आप इस
for (int i = 0; i < N; i++)
for (int j = i; j < N; j++)
…
आप पहली बार भीतरी पाश में एन बार पुनरावृति जाएगा, तो N-1, तो एन 2, आदि, जो एन (एन 1) के कुल योग/2 करते हैं । यह लूप ओ (एन²) में चलता है, जो बाहरी पाश का वर्ग है।
आपके मामले में, अपने कोड
for (int i = 0; i < N; i++)
for (int j = i; j < N; j++)
c++;
के बराबर है के बाद से हर पूर्णांक सकारात्मक के लिए हम n² ≥ एन है और संकलक काफी चतुर को नोटिस कि यह कोई मतलब नहीं है बाहरी पाश निरंतर चलाने के लिए किया जाना चाहिए अगर मैं एन से बड़ा हूं तो जटिलता वास्तव में ओ (एन²) है।
आप N और c अपने कार्यक्रम चलाता है के बाद मुद्रित करते हैं, तो आप देखेंगे कि जब N दोगुनी हो जाता है, c लगभग द्वारा 4 (2²) गुणा किया जाता है:
N = 1, c = 1
N = 2, c = 3
N = 4, c = 10
N = 8, c = 36
N = 16, c = 136
N = 32, c = 528
N = 64, c = 2080
N = 128, c = 8256
N = 256, c = 32896
N = 512, c = 131328
N = 1024, c = 524800
N = 2048, c = 2098176
पारदर्शी स्पष्टीकरण के लिए धन्यवाद! – RobotRock
औपचारिक रूप से पुनरावृत्तियों की संख्या पता करने के लिए और विकास के क्रम:
क्यों आप बाहरी पाश में 'एन * n' उपयोग करते हैं? लूप खत्म होने के बाद बस 'सी' प्रदर्शित करें; जो आपको बताएगा कि आपको क्या जानना है। –
जटिलता बिगो (एन^3) –
@Tudor Vintilescu आप इस के पीछे अपने तर्क की व्याख्या कर सकते है? – RobotRock