छोरों

Question

के लिए नेस्ट की बड़ी-ओ जटिलता मैं निम्नलिखित की जटिलता लेकर संदेह में हूँ (निरंतर समय में भीतरी लूप के अंदर प्रदर्शन किया ऑपरेशन है):

for(int i=0; i<n; i++) 
    for(int j=i; j<n; j++) 

इस हे है (एन^2) या ओ (एन)? मैं ओ (एन^2) आंकड़ा। कोई विचार? ,

for(int i=0; i<n; i++) 
    for(j=0; j<i; j++) 

Answer 1

निश्चित रूप से O(n squared) निश्चित रूप से:

भी निम्नलिखित मुझे उत्सुक बनाता है। दोनों मामलों के लिए सारांश स्पष्टीकरण: 1 + 2 + ... + n n(n+1)/2 है, यानी (n squared plus n)/2 (और बड़े-ओ में हम दूसरे, कम हिस्से को छोड़ देते हैं, इसलिए हमें एन वर्ग/2 के साथ छोड़ दिया जाता है जो निश्चित रूप से है O(n squared))।

Answer 2

आप सही हैं, उन नेस्टेड लूप अभी भी ओ (एन^2) हैं। संचालन की वास्तविक संख्या कुछ (एन^2)/2 के करीब है, जो निरंतर 1/2 कारक को छोड़ने के बाद, ओ (एन^2) है।