Время выполнения 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 ^ 2 также, поскольку мы повторяем первый цикл n раз, а второй - n раз? Любая помощь будет оценена.

Спасибо!

Answer 1

В этом случае не похоже, что они вложенные. Есть 2 цикла, разделенных if / else. В этом случае это будет O (n).

Если бы циклы while были вложенными и основывались на размере ввода, это действительно было бы O (n ^ 2). Не важно, какой тип цикла вы используете, а скорее тот факт, что вы зацикливаетесь на вводе размера n.

Answer 2

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

Если в первом массиве n элементов, а во втором массиве m элементов m, тогда время выполнения равно O (n * m)

равно O (n * n)

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

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

В этом случае время выполнения равно O (n) + O (m), что равно O (n), если n больше или равно m и O (m) если m больше или равно n.

Answer 3

Как вы сказали, вложенный цикл запускается в O (n²).Обозначение для определения того, как быстро будут работать два из них в последовательности, - O (2n²).Обозначение для запуска двух циклов while каждый раз n равно O (2n).