函数 exe:log(n) 中的运行时间是多少
int fun(int n) {
int count = 0;
for (int i = n; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count += 1;
return count;
}
最佳答案
这不是 O(log n)，而是 O(n)。你可以这样想:外循环每次运行都会将剩余的数据(原来是n)送入内循环进行处理，然后删除其中的一半。内循环在其处理的数据中显然是线性的。
在第一次迭代时，外循环将整个 n 发送到内循环，从而“支付”n 个处理步骤。
在第二次迭代时，还剩下 n/2 数据，因此内部循环为其支付 n/2 ；它总共支付了 1.5n。
在下一次迭代时，还剩下 n/2/2 == n/4 数据，内循环为此支付额外的 n/4，因此总共 1.75n。
以此类推，直到整个n已经支付了两次，所以成本为2n，即O(n)，实际上甚至是ϴ(n) .
关于c - fun() 的时间复杂度是多少？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53986306/