что такое временная сложность 2 для цикла, записанного в одном цикле

Question

Привет, я просто подумал, что если я напишу цикл, как указано ниже, какова будет временная сложность этого. это будет o (n ^ 2) или просто o (n)

for(var i=0,j=0;i<arr1.length || j<arr2.length;i++,j++)
{
    //some code here
}

Answer 1

Сложность по времени составляет O (max (m, n)) с m и n размером arr1и arr2 соответственно.

В вашем цикле for вы увеличиваете значения i и j после цикла.Цикл for останавливается, если оба i >= arr1.length и j >= arr2.length.Поскольку i и j всегда имеют одно и то же значение (за исключением момента между приращениями i и j), оно заканчивается, если оба значения i и j достигли конца своего соответствующего списка.

Здесь мы делаем предположение, что увеличение i и j выполняется в постоянное время (хорошо для очень больших чисел, что займет O (b) с b (число битов числа с произвольным размером), и что тело цикла for содержит только инструкции, которые также выполняются в постоянное время.

Answer 2

Предполагая, что в //some code here больше нет циклов, сложность времени равна O(N), потому что цикл прерывается, как только i<arr1.length и j<arr2.length, и оба i и j увеличиваются на каждой итерации. Он будет работать для Math.max(arr1.length, arr2.length) итераций.

Для

i<arr1.length || j<arr2.length

должно быть false (и, следовательно, больше никаких итераций), должно быть

i >= arr1.length
// and
j >= arr2.length