什么是大 O 表示法（时间复杂度）非嵌套 for 和 while 循环？

Question

所以这是代码：

while(n>0) {
n /=2;
}
for(let i = 0; i < n; i ++) {
// Do something
}

while 循环的时间复杂度为 log base 2 n，而 for 循环的时间复杂度仅为 n。那么，是 O(log2n) 还是 O(n) ？答案是哪一个？

Answer 1

您对每个循环的假设都是正确的，但是当放在一起时，您不能简单地将它们加起来以获得总时间复杂度。这些主要由代码中最有影响力的部分决定，并且

O(n)

将完全主导总运行时间，使得第一个

O(log2 n)

循环从长远来看可以忽略不计，因此第一个简单的答案将是

O(n)

。

但是，请考虑第一个循环进行的操作会影响第二个循环，特别是在此处通过更改作为第二个循环的主要比例因子的

n

变量。

到第一个循环结束时，

n

将是0或负数（当它为正时，你会继续循环），这意味着如果

i < n

从零开始，循环条件

i

永远不会为真，所以第二个循环永远不会执行一次。因此它的时间复杂度不依赖于任何东西，所以它会是

O(1)

。在这种情况下，完整代码的复杂度将是

O(log2 n)

，因为第一个循环的运行时间将主导第二个循环。

一般来说，尝试查看完整的代码而不是各个部分，因为它们经常相互交互，并且仅当您可以确定一个部分的执行不会影响另一个部分和块的执行时才进行单独分析真的很独立。