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

Question

我在网上遇到了这个时间复杂的例子,我有点困惑.

x = n
while ( x > 0 ) {
    y = x
    while ( y > 0 ) {
        y = y - 1
    }
    x = x / 2
 }

答案表示为O(n).我想知道为什么它不是O(nlogn).我之所以这么说是因为外环看起来是对数的,而内环似乎是线性的.如果y = n(而不是x),时间复杂度THEN是否为O(nlogn)？如果是这样,为什么？

Answer 1

它传递了多少时间y=y-1？这将衡量复杂性,对吗？

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

所以它通过n + n/2 + n/4 ...总计达2n.

因此总复杂度为O(n).

不要被愚弄,内环是线性的,但不是独立于外环.

Answer 2

内环实际上是线性的,但每次迭代都不采取n步骤,但是x当前值x迭代减半的步骤,这意味着可以进行更精细的分析.您高估了内循环的成本.因此,界限

O(n log n)

也是对的,但是

O(n)

是一个较小的界限.通过推断i内循环的第th次迭代,可以看出较小的界限

n / 2^i

脚步; 运动界限O(n)遵循以下事实:分母之和是几何级数,它收敛于常数2.