इस कोड की जटिलता क्या है जिसका लूप के लिए नेस्टेड बार-बार अपने काउंटर को दोगुना करता है?

Question

पुस्तक में प्रोग्रामिंग साक्षात्कार एक्सपोज़ड यह कहता है कि नीचे दिए गए कार्यक्रम की जटिलता ओ (एन) है, लेकिन मुझे समझ में नहीं आता कि यह कैसे संभव है। क्या कोई समझा सकता है कि यह क्यों है?

int var = 2; 
for (int i = 0; i < N; i++) { 
    for (int j = i+1; j < N; j *= 2) { 
     var += var; 
    } 
} 

Answer 1

आपको इसे देखने के लिए थोड़ा गणित चाहिए। आंतरिक लूप Θ(1 + log [N/(i+1)]) बार (1 +i >= N/2, [N/(i+1)] = 1 और लॉगरिदम 0 है, फिर भी लूप एक बार फिर से सक्रिय होता है) के लिए आवश्यक है। j मान लेता है (i+1)*2^k जब तक यह N के रूप में कम से कम के रूप में बड़ा है, और

(i+1)*2^k >= N <=> 2^k >= N/(i+1) <=> k >= log_2 (N/(i+1)) 

गणितीय विभाजन का उपयोग कर। तो अद्यतन j *= 2 को ceiling(log_2 (N/(i+1))) बार कहा जाता है और स्थिति 1 + ceiling(log_2 (N/(i+1))) बार चेक की जाती है। इस प्रकार हम कुल काम

N-1         N 
∑ (1 + log (N/(i+1)) = N + N*log N - ∑ log j 
i=0         j=1 
         = N + N*log N - log N! 

अब लिख सकते हैं, Stirling's formula हमें

log N! = N*log N - N + O(log N) 

तो हम पाते हैं की कुल काम वास्तव में O(N) है बताता है।

Answer 2

@ डैनियल फिशर का जवाब सही है।

मैं इस प्रकार इस तथ्य यह एल्गोरिथ्म के सटीक चलने का समय है कि जोड़ना चाहते हैं:

जिसका मतलब है:

Answer 3

बाहरी पाश n बार चलाता है। अब यह सब आंतरिक पाश पर निर्भर करता है।
आंतरिक लूप अब मुश्किल है।

चलें का पालन करें:

i=0 --> j=1    ---> log(n) iterations 
... 
... 
i=(n/2)-1 --> j=n/2  ---> 1 iteration. 
i=(n/2) --> j=(n/2)+1 --->1 iteration. 

---

i > (n/2)   ---> 1 iteration 
(n/2)-1 >= i > (n/4) ---> 2 iterations 
(n/4) >= i > (n/8) ---> 3 iterations 
(n/8) >= i > (n/16) ---> 4 iterations 
(n/16) >= i > (n/32) ---> 5 iterations 

(n/2)*1 + (n/4)*2 + (n/8)*3 + (n/16)*4 + ... + [n/(2^i)]*i 

    N-1         
n*∑ [i/(2^i)] =< 2*n 
    i=0 

--> O(n)