नेस्टेड लूप का बिग-ओ क्या है, जहां आंतरिक पाश में पुनरावृत्तियों की संख्या बाहरी लूप के वर्तमान पुनरावृत्ति द्वारा निर्धारित की जाती है?

Question

निम्नलिखित नेस्टेड लूप की बिग-ओ टाइम जटिलता क्या है:

for(int i = 0; i < N; i++) 
{ 
    for(int j = i + 1; j < N; j++) 
    { 
     System.out.println("i = " + i + " j = " + j); 
    } 

} 

क्या यह O (N^2) अभी भी होगा?

Answer 1

हाँ, यह अभी भी ओ (एन^2) है, इसमें एक छोटा निरंतर कारक है, लेकिन यह ओ नोटेशन को प्रभावित नहीं करता है।

Answer 2

हां, यह एन वर्ग होगा। चरणों की वास्तविक संख्या 1 से एन की राशि होगी, जो .5 * (एन -1)^2 है, अगर मुझे गलत नहीं लगता है। बिग ओ केवल उच्चतम घातीय और कोई स्थिरांक खाते में नहीं लेता है, और इस प्रकार, यह अभी भी एन वर्ग है।

Answer 3

हां। बिग-ओ की परिभाषा याद: हे (च (एन)) परिभाषा के द्वारा कहा गया है कि रन टाइम टी (एन)≤ kf (एन) कुछ निरंतर कश्मीर के लिए। इस मामले में, चरणों की संख्या (एन -1) + (एन -2) + ... + 0 होगी, जो 0 से एन -1 के योग को पुनर्व्यवस्थित करती है; यह

टी (एन) = (एन -1) ((एन -1) +1)/2।

पुनर्व्यवस्थित करें और आप देख सकते हैं कि टी (एन) हमेशा ≤ 1/2 (एन ²) होगा; परिभाषा के अनुसार, इस प्रकार टी (एन) = ओ (एन ²)।

Answer 4

यदि आप System.out.println को अनदेखा करते हैं तो यह एन वर्ग है। यदि आप मानते हैं कि उसके द्वारा लिया गया समय उसके आउटपुट में रैखिक होगा (जो यह निश्चित रूप से नहीं हो सकता है), मुझे संदेह है कि आप ओ ((एन^2) * लॉग एन) के साथ समाप्त हो जाते हैं।

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

Answer 5

यदि आपके पास एन = 10 था, तो आप पुनरावृत्ति होंगे: 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1। (यह है: दस पुनरावृत्तियों और नौ पुनरावृत्तियों और आठ पुनरावृत्तियों ... आदि)। 8 (:

1: (10), 2: (9 + 1), 3

अब, आप इसके अलावा कितनी बार आप एक एन प्राप्त कर सकते हैं (10 उदाहरण में) में खोजने की जरूरत है +2), 4: (7 + 3), 5: (6 + 4)। जो 5 गुना है ... और 5 पुनरावृत्तियों को आराम देता है।

अब आप समझ जाएंगे कि आप पांच दसियों + 5:

10 (5) + 5

च (एन) (या एन), हम आसानी से देख सकते हैं कि यह होगा के संदर्भ में:

एफ (एन) = एन (एन/2) + एन/2 = (एन^2)/2 + एन/2 = (एन^2 + एन)/2 ... यह बिल्कुल जटिलता है इन घोंसला लूप।

लेकिन, बिग ओ के असम्बद्ध व्यवहार पर विचार करते हुए, हम एफ (एन) के कम महत्वपूर्ण मूल्यों से छुटकारा पा सकते हैं, जो एकल एन और denominator हैं।

परिणाम: O (n^2)

Answer 6

AFAIL, बाहरी लोगों के माध्यम से आंतरिक पाश से शुरू कर दिया जा रहा है नेस्टेड लूप जटिलता की गणना के लिए पर्याप्त तरीका है।