为什么这段代码的时间复杂度是 O(n) 而不是 O(log n)

2024-09-08 • 问答

以下代码的时间复杂度为 O(n log n) 我认为对于外循环日志 n 但是对于内部循环 n。所以，O(n logn )

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

但是下面代码的时间复杂度是 O(n)

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

为什么上面代码的时间复杂度是 O(n)？

因为内循环的迭代次数减少了与x减少相同的比例。总迭代次数将始终约为 2n - 1（当 n 是 2 的幂时准确，对于其他数字会有所偏差）。 Big-O 忽略总和的系数和低阶分量，所以是 O(n)。

例如，当n == 16时，外循环的第一次迭代执行内循环的16次迭代。第二次迭代执行 8，然后是 4，依此类推。所以总数是16+8+4+2+1 == 31。