O(n)vs O(nlogn)时间复杂度

过了多少次 y=y-1 ?这将衡量复杂性,对吗?

• 当x=n时,它经过n次。
• 当x=n/2时,它通过n/2次。
• 当x=n/4时,它通过n/4次。
• 。。。

所以它通过了n+n/2+n/4。。。总计为2n。

因此,总复杂度为O(n)。

别傻了,内环是线性的,但不是独立于外环的。

内部循环确实是线性的,但每次迭代不需要 n 步骤,但 x 当前值的步骤 十、 它以迭代方式减半,这意味着可以进行更精细的分析。您高估了内环的成本。因此,边界

O(n log n)

也是正确的,但是

O(n)

是一个较小的界限。通过推理可以看出较小的界限 i -th公司 内部循环的迭代需要

n / 2^i

步骤;的运行时界限 O(n) 根据分母之和是 geometric series ,收敛到常数 2 。