谁能告诉我代码的时间复杂度
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
外循环使用 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)。