两个相关 for 循环的复杂度，外层循环的复杂度为 log n

问题

计算该算法的复杂度：

 for(i=n; i>1;i=i/2)
   for(j=i;j<n;j++){
         statement;
   }

我之前在这个主题上做了什么：

第一个循环运行 logn 次。 第二个循环运行 n-i 次，其中 i 从 n 开始，并在每次外循环迭代中更改为 i/2。所以内循环是这样运行的：

n-n                             0 times

n - n/2                        n/2 times

n - n/4                        3n/4 times

n - n/8                        7n/8 times

n - n/16                     15n/16 times

依此类推，直到

n - 1 times

所以一般术语是n * ((2^n)-1)/(2^n)

现在这个序列既不是算术序列也不是几何序列。所以公式为n/2 * (a+l)不能应用于其上。我该如何进一步继续这个解决方案，或者如果它是错误的，那么正确的方法是什么。

注：如果n/2*(a+l)应用时，所得的复杂度为-n/(2^n) = O(2^n).

你走在正确的轨道上。正如您所提到的，内部循环将运行log n次。所以，它运行的总次数是：

    (n - n/2) + (n - n/4) + ... (log n) times
  = n*(log n) - (n/2 + n/4 + n/8 + ... up to 1)
  = n*(log n) - n*(1/2 + 1/4 + ...)
 <= n*(log n) - n because (1/2 + 1/4 + ...) is 1 even if we take all terms till infinity (G.P)
  = n(log n - 1), which is O(n*log(n))

请记住，在计算复杂性时，您总是在寻找上限，而不是精确的数字。