मेरे कार्य की समय जटिलता क्या है?</p> <pre><code>void what(int n) { int i; for (i = 1; i <= n; i++) { int x = n; while (x > 0) x -= i; } } </code></pre> <p>खैर, पाश के लिए पहले स्पष्ट रूप से <code>O(n)</code> है:

Question

जटिलता के बारे में अध्ययन, मैं इस एक के साथ संघर्ष कर रहा हूँ शुरू कर दिया। पहला पुनरावृत्ति O(n) है, दूसरा एक O(n/2) है .. और log(n) बार मुझे लगता है कि? जिसका अर्थ है O(n) * O(log(n)) = O(n * log(n)) complexity। क्या मुझे यह अधिकार मिला?

संपादित करें: (डुप्लिकेट नहीं) मुझे पता है कि बिग ओ क्या है। मैंने एक विशिष्ट मामले में सही मूल्यांकन पूछा है।

Answer 1

बाहरी पाश n बार चलाता है।

प्रत्येक पुनरावृत्ति के लिए, आंतरिक लूप n/i बार चलाता है।

रन की कुल संख्या है:

n + n/2 + n/3 + ... + n/n 

Asymptotically (पूर्णांक गणित गोलाई अनदेखी), इस सरल रूप में

n * (1 + 1/2 + 1/3 + ... + 1/n) 

इस श्रृंखला शिथिल n * log(n) की ओर अभिमुख।

इसलिए जटिलता ओ (एन.लॉग (एन)) जैसा कि आप उम्मीद करते थे।

Answer 2

पहले भीतरी पाश n बार
दूसरा भीतरी पाश चलाता n/2 बार ..
तीसरे भीतरी पाश n/3 बार
चलाता पिछले एक एक बार

तो n + n/2 + n/3 + ... + 1 = n(1+1/2+1/3+1/4 + ... +1/n) चलाता चलाता है।

यह n हार्मोनिक श्रृंखला है, जो एक अच्छा बंद फार्म प्रतिनिधित्व नहीं है की राशि से गुणा किया जाता। लेकिन जैसा दिखाया गया है here यह O(log(n)) है। तो कुल मिलाकर एल्गोरिदम O(n log(n))

Answer 3

परीक्षण और ग्राफिक्स द्वारा इसका प्रयास। लॉग 2 बनाम लॉग 2 प्लॉट काफी रैखिक दिखता है। रैखिक ओ (एन) से अधिक और ओ से कम (एन * लॉग (एन)) के बीच कुछ। अपना खुद का निष्कर्ष निकालें।

[संपादित करें]

गणितीय व्युत्पन्न सूत्रों का उपयोग करना, ओ() की गणना (एन * लॉग (एन)) हे की एक ऊपरी बाध्य है। यह "लूप पुनरावृत्तियों के अंश" का उपयोग करता है जो एक अंश द्वारा गिनती बढ़ाता है और नहीं 1. उदा। जब n 6, पुनरावृत्ति संख्या 6 + 3 + 2 + 1,5 + 1,2 + 1 = 14,7 बजाय वास्तविक से छोरों 6 + 3 + 2 + 2 + 2 + 1 = 16. यह अंतर अपेक्षाकृत कम महत्वपूर्ण n के रूप में बढ़ जाती है, इस प्रकार है ओ (एन * लॉग (एन)) से थोड़ा कम विकास। इसलिए कोड को अनदेखा करके पूर्णांक गणित का उपयोग नहीं करता है, हमारे पास एक और अधिक चुनौतीपूर्ण प्रश्न है।

---

unsigned long long what(int n) { 
    unsigned long long cnt = 0; 
    int i; 
    for (i = 1; i <= n; i++) { 
    int x = n; 
    while (x > 0) { 
     x -= i; 
     cnt++; 
    } 
    } 
    return cnt; 
} 

void wtest(int n) { 
    unsigned long long cnt = what(n); 
    printf("%d %llu\n", n, cnt); 
    fflush(stdout); 
} 

void wtests(void) { 
    int i = INT_MAX/2 + 1; 
    while (i > 0) { 
    wtest(i); 
    i /= 2; 
    } 
} 

int main(void) { 
    wtests(); 
    return 0; 
} 

आउटपुट

1073741824 23567395117 
536870912 11411566988 
268435456 5519718329 
134217728 2666826555 
67108864 1286897093 
33554432 620190504 
16777216 298466265 
8388608 143418602 
4194304 68802063 
2097152 32947406 
1048576 15746897 
524288 7510048 
262144 3573331 
131072 1695816 
65536 802493 
32768 378537 
16384 177921 
8192 83286 
4096 38803 
2048 17973 
1024 8275 
512 3782 
256 1713 
128 765 
64 337 
32 145 
16 61 
8 24 
4 9 
2 3 
1 1 

Answer 4

एक विकल्प के रूप में, अपने एल्गोरिथ्म के भीतरी while लूप के पुनरावृत्तियों की संख्या का विश्लेषण करने के लिए एक चर प्रतिस्थापन y = n - x सिग्मा अंकन के बाद का उपयोग करें ।

ऊपर overestimates, प्रत्येक भीतरी जबकि पाश, मामलों के लिए 1 द्वारा पुनरावृत्तियों की संख्या जहां n-1i की एक बहु नहीं है, अर्थात जहां (n-1) % i != 0 के लिए। जैसे ही हम आगे बढ़ते हैं, हम मान लेंगे कि (n-1)/ii के सभी मानों के लिए एक पूर्णांक है, इसलिए आंतरिक while लूप में पुनरावृत्तियों की कुल संख्या को अधिक महत्व देना, इसके बाद नीचे (i) पर कम या बराबर चिह्न शामिल है। हम सिग्मा अंकन विश्लेषण के साथ आगे बढ़ना:

जहां हम, (ii) पर, n approximated है वें harmonic number जुड़े अभिन्न द्वारा। इसलिए, आप एल्गोरिदम O(n·ln(n)) में, asymptotically चलाता है।

---

asymptotic व्यवहार छोड़कर और कलन विधि की वास्तविक विकास का अध्ययन, हम सटीक (n,cnt) का अच्छा नमूना डेटा (जहां cnt भीतरी पुनरावृत्तियों की संख्या है) जोड़े @chux द्वारा (अपने जवाब को देखें) का उपयोग कर सकते हैं, और तुलना करें ऊपर से पुनरावृत्तियों की अनुमानित संख्या के साथ, यानी n(1+ln(n))-ln(n)। यह स्पष्ट है कि अनुमान वास्तविक गणना के साथ अच्छी तरह से सामंजस्यपूर्ण है, नीचे दिए गए प्लॉट या this snippet for the actual numbers देखें।

---

अंत में ध्यान दें कि यदि हम ऊपर 1/i से अधिक राशि में n->∞ करते हैं, जिसके परिणामस्वरूप श्रृंखला infinite harmonic series है, जो है, दिलचस्प पर्याप्त, अलग-अलग। उत्तरार्द्ध के लिए सबूत इस तथ्य का उपयोग करता है कि असीमित गैर-शून्य शब्दों में स्वाभाविक रूप से अनंत है। अभ्यास में, हालांकि, पर्याप्त रूप से बड़े लेकिन अनंत एन, ln(n) के लिए योग का उचित अनुमान है, और यह विचलन हमारे एसिम्प्टोटिक विश्लेषण के लिए प्रासंगिक नहीं है।

---