这段代码的时间复杂度根据我来说是 O(nlogn)

Question

谁能告诉我代码的时间复杂度

count = 0

for (int i = n; i > 0; i /= 2)
    for (int j = 0; j < i; j++)
        count++;

请给我时间复杂度。因为根据我的计算，外循环将 n 除以 2，所以它运行了 logn 次，而内循环运行了 n 次，所以时间复杂度是 nlogn，但根据这个问题的关键，时间复杂度是 n。 谁能澄清一下如果我错了请纠正我。

我尝试了所有的人工智能工具，一切都给了我nlogn

Answer 1

外循环使用 i 进行 log2(n) 次。

内循环从 0 到 i，所以你得到

n/1 + n/2 + n/4 + ... + n/(2^k)

iterations，其中 k 是外部迭代的次数。这与

相同

n * (1/(2^0) + 1/(2^1) + 1/(2^2) + ... + 1/(2^k))

和

n *（从 k = 0 到 log2(n) of 1/(2^k) 的总和）。

这是趋于 2 的几何级数的 n 倍，所以总的来说，你有 n * 2，因此，O(n)。