big-o - 如果一个函数内部有 2 个 for 循环（不是嵌套的），那么 bigOh 对整个函数来说仍然是 O(n) 吗？

Question

在函数内部有不同的循环不会导致 BigOh 相乘，对吗？

例子：

function() {
    for(int i = 0; i < n; i++) {
        //logic here
    }

    for(int i = 0; i < n; i++) {
        //logic here
    }
}

score 1 · Accepted Answer

对此进行了很好的讨论（即一般参考），但是是的，您是正确的，您在问题中拥有的功能将是 O(n)。

技术上 O(2n) 减少到 O(n)

score 1 · Accepted Answer

是的，它仍然是 O(n)，因为你会有 O(n+n)，即 O(2n)，但我们可以忽略 2，因为它的影响可以忽略不计。但如果你有

for (...){
  for(...){
    //code here
  }
}

那么它将是 O(n^2)

score -1 · Accepted Answer

请参阅有关堆栈溢出的这篇文章，其中解释了为什么它的 O(N)。

3 回答 3