2个嵌套while循环的运行时间

Question

我还有一个关于循环的问题。我知道 2 个 for 循环的运行时间为 O(n^2)，因为您迭代列表 n * n 次。

但是两个 while 循环呢？

While (array1 is not empty)

    if(~~~)
        do ~~~
    else(~~~)
        do ~~~

  while (array2 is not empty)

    if(~~~)
        do ~~~
    else(~~~)
        do ~~~

所以一个 while 循环嵌套在另一个 while 循环内。由于我们迭代第一个循环 n 次和第二个循环 n 次，这是否也会使运行时间 n^2 ？任何帮助将不胜感激。

谢谢！

Answer 1

在这种情况下，它们看起来并不像嵌套的。有 2 个循环，由 if/else 分隔。在这种情况下，它将是 O(n)。

如果 while 循环是嵌套的并且基于输入大小，那么它确实是 O(n^2)。您使用的循环“类型”并不重要，重要的是您正在循环大小为 n 的输入。

Answer 2

正如您所说，嵌套 for 循环的运行时间为 O(n²)。用于确定其中两个序列的运行速度的符号是 O(2n²)。运行两个 while 循环各 n 次的表示法是 O(2n)。

Answer 3

while (array1 isn't empty){
     while (array2 isn't empty){
         //code goes here
     }
}

如果第一个数组有 n 个元素，第二个数组有 m 个元素，则运行时间为 O( n * m )

在 n 和 m 相同的特殊情况下，则为 O( n * n )

while (array1 isn't empty){
//code
}

while (array2 isn't empty){
//code
}

在这种情况下，运行时间是 O(n) + O(m)，如果 n 大于或等于 m，则为 O(n)；如果 m 大于或等于 n，则为 O(m)。