什么是这个伪代码的运行时间

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)。