这个伪代码的运行时间是多少

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