同一范围内的多个 for 循环如何影响程序的大 O 表示法？

Question

假设我有一个如下所示的程序：

var foo = 10;

for(var i = 0; i < foo; i++){
    console.log('first loop');
}

for(var j = 0 j < foo; j++){
    console.log('second loop');
}

现在，根据我对大 O 表示法的一般理解，我们根据 N 输入的大小来衡量程序的效率（也就是运行需要多长时间）。因此，如果 'j' 循环嵌套在 'i' 循环中，这将使它成为 n^2，但是因为两个循环都在同一范围内，所以运行时间仍然是 O( N).这个评估是否正确？

Answer 1

是的，这是正确的

只是要指出 "how long it takes to run" 这个短语对于 Big O

不是 100% 准确

describes the limiting behavior of a function when the argument tends towards a particular value or infinity. https://en.wikipedia.org/wiki/Big_O_notation

O(N) + O(N) = O(N)
O(N) + O(M) = O(max(N,M))

Answer 2

这仍然是线性搜索，O(N)，因为两个循环根本不相互作用。

从技术上讲，数组访问是常数 O(1)，它的搜索在时间上是线性的。

O 符号基本上用于衡量算法的复杂性，范围在这里无关紧要。

Answer 3

是的，你的假设是正确的，

在这两个循环中完成的基本操作是

循环 1，迭代 1
循环 1，迭代 2 ......
循环 1，迭代 10
循环 2，迭代 1 ......
循环 2，迭代 10

对于N阶的每个循环，有N个写操作。

所以总时间复杂度将是 O(N) + O(N) 但由于常量被忽略所以复杂度是 O(N)

同一范围内的多个 for 循环如何影响程序的大 O 表示法？

How does multiple for loops in the same scope affect a program's big O notation?

javascript

big-o