हे (एन) क्रम एल्गोरिथ्म

Question

नीचे एल्गोरिथ्म क्रम O(n) हमारे प्रोफेसर के अनुसार, हालांकि मैं, के रूप में उलझन में हूँ क्यों यह O(n log(n)) नहीं है, क्योंकि बाहरी पाश log(n) गुना तक चला सकते हैं और भीतरी पाश ऊपर चला सकते हैं n बार।

Algoritme Loop5(n) 
i = 1 
while i ≤ n 
    j = 1 
    while j ≤ i 
     j = j + 1 
    i = i∗2 

Answer 1

आपका प्रोफेसर सही था, चलने का समय O(n) है।

बाहरी जबकि पाश की i वें यात्रा में, जब हम k=0,1,...,log n के लिए i=2^k है, भीतरी, जबकि लूप O(i) पुनरावृत्तियों में आता है। (जब मैं log n कहते हैं कि मैं आधार -2 लघुगणक log_2 n मतलब है।)

चलने का समय k=floor(log n) के लिए O(1+2+2^2+2^3+...+2^k) है। यह O(2^{k+1}) पर है जो O(2^{log n}) है। (यह formula for the partial sum of geometric series से है।)

क्योंकि 2^{log n} = n, कुल चलने का समय O(n) है।

रुचि के लिए, यहां एक सबूत है कि दो शक्तियों की शक्तियों का वास्तव में योग जो मैं दावा करता हूं। (यह एक सामान्य परिणाम का एक बहुत ही खास मामला है।)

दावा। किसी भी प्राकृतिक k के लिए, हमारे पास 1+2+2^2+...+2^k = 2^{k+1}-1 है।

सबूत। ध्यान दें कि (2-1)*(1+2+2^2+...+2^k) = (2 - 1) + (2^2 - 2) + ... + (2^{k+1} - 2^k) जहां के लिए सभी 2^ii=0 और i=k+1 को छोड़कर रद्द करें, और हमें 2^{k+1}-1 के साथ छोड़ दिया गया है। QED।