的一段代碼

Question

計算的大O符號的複雜性能否請你解釋如何計算下列段的大O的複雜性：

i := n; 
while i > 1 do 
    begin 
    for j:= i div 2 + 1 to i do 
     begin 
     k := 2; 
     while n >= k do 
      k := k * k 
     end; 
    i := i div 2 
    end; 

（這是帕斯卡，但語言並不重要位置。 ） 正確的答案是n*log(log(n))，但我不知道如何到達那裏。

Answer 1

開始與內循環：

k := 2; 
    while n >= k do 
     k := k * k 

這直到它到達n值2,2 ，2 ，2 ，..分配給k。這是O（日誌（日誌（n））的，因爲，如果我們調用的迭代的數目m，它迭代，直到

 
22m > n → log(22m) > log(n) → log(log(22m)) > log(log(n)) → 

→ m > log(log(n)) → m = log(log(n)) + 1 

然後

for j:= i div 2 + 1 to i do 
    begin 
    //O(log(log(n)) 
    end; 

這具有I/2次迭代，所以它爲O（（I/2）的日誌（日誌（N）））

i := n; 
while i > 1 do 
    begin 
    // (i/2) log(log(n)) 
    i := i div 2 
    end; 

這具有爲O（log（N））O的迭代（第（i/2）的日誌（日誌（N））），其總計爲

 
    O((n/2) log(log(n)) + (n/4) log(log(n)) + (n/8) log(log(n)) + (n/16) log(log(n)) + ...) = 
= O((1/2 + 1/4 + 1/8 + 1/16 + ...) n log(log(n))) = 
= O(0.1111111…2 n log(log(n))) = 
= O(n log(log(n))) 

（0.11111 ... = 1，就像0.999 ... = 1，但它並不重要O（）反正）