有人可以解释一下您如何使用正确的符号分析此代码的运行时间吗?

Question

for (int i=1; i<n; i=i*2)
{
for (int i=0; i<n; i=i+1)
{
if (i<1000)
cout << i << "n";
}
}

我不明白你是如何用求和来表达循环以找到运行时间的。你如何确定求和的边界？

Answer 1

只需查看每个循环的迭代次数即可。 外部循环从 1 到 n，每次加倍i，因此它确实记录了₂n次迭代。内部循环从 0 到 n 每次加1，因此它会进行n次迭代。

把它们放在一起，你会得到O(n logn(