询问下述C++算法的时间复杂度：我认为是O(n)但书籍答案为O(nlogn)

首先看给出的C++代码：

int k = 0;
for (int a = n; a >= 1; a /= 2)
  for (int b = a; b >= 1; b--)
    k++;
cout << k;

我们来拆解总执行次数：

• 外层循环：a从n开始，每次除以2直到a >=1，执行次数为log₂n + 1次（比如n=8时，a取8、4、2、1，共4次）。
• 内层循环：每次外层循环对应的内层循环执行次数等于当前的a值，因此总执行次数是n + n/2 + n/4 + ... + 1。

这是首项为n、公比为1/2的等比数列求和，结果为2n - 1（当n是2的幂时），即使n不是2的幂，总和也小于2n。因此该算法的时间复杂度是O(n)。

你提到书籍给出的答案是O(nlogn)，大概率是题目代码存在差异——比如如果内层循环是b从1到n而非a，总次数才会是n*(log₂n+1)，对应O(nlogn)的复杂度。

内容的提问来源于stack exchange，提问作者Andrei Morgovan