什麼是這個僞代碼的運行時間

Question

i = 1; 
while (i <= n) 
    j = i; 
    x = x+A[i]; 
    while (j > 0) 
    y = x/(2*j); 
    j = j/2; // Assume here that this returns the floor of the quotient 
    i = 2*i; 
return y; 

我不知道我的答案，我得到了O（n ）。

Answer 1

讓我們刪除x和y變量，因爲它不影響複雜性。

i = 1; 
while (i <= n) 
    j = i;  
    while (j > 0) 
     j = j/2; 
    i = 2*i; 

1. 在內環您每次分j 2，所以實際上它不屬於班輪是O(logn)。例如，當j是16時，您將執行5 (O(log16)+1)步驟：8,4,2,1,0。
2. 在外層循環中，你每次乘以i乘以2，所以它也是O(logn)。

因此整體複雜度將是O(logn * logn)。