Если я использую две переменные для итерации по двумерному массиву, это все еще O (n ^ 2) время сложность?

Question

for (let i = 0; i < array.length; i += 1) {
  const row = array[i];
  for (let j = 0; j < row.length; j += 1) {
      const el = row[j];
  }
}

Типичный способ перебора матрицы nxn двумерного массива, и я считаю, что O (n ^ 2) временная сложность.

Если бы я сделал это вместо

let count = 0;
let i = 0;
let j = 0;
const n = arr.length;
const max = n * n;

while (count !== max) {
  const ele = arr[i][j];
  if (j === n - 1) {
    j = 0;
    i += 1;
  } else j += 1;
  count += 1;
}

Будет ли это все еще O (n ^ 2)?Отчасти глупый вопрос, я думаю, что ответ - да, но я просто хочу перепроверить.Очевидно, что первый метод намного понятнее, но тогда и хорошая временная сложность также хороша.

Answer 1

Ну, во-первых, это не действительно O (n ² ).

Big-O показывает производительность алгоритма в худшем случаедает представление о том, как увеличивается время его выполнения с увеличением количества элементов, обрабатываемых алгоритмом.

В случае двумерной матрицы, хотя матрица действительно квадратная (или, по крайней мере,(прямоугольник), здесь не совсем уместно использовать длину матрицы как n.Скорее, вы должны использовать количество ячеек в матрице (i x j).

Двумерная матрица, по сути, представляет собой массив массивов, и ваш алгоритм просто проходит по каждомуячейка один раз, делая его O (n) в обоих случаях.Вы могли бы сказать, что это O (i x j), но это все еще линейный алгоритм.

Answer 2

Дано n = макс. (Array.length, array [0] .length) :

Да - они оба O (n ^2) .Несмотря на то, что это один цикл, количество элементов, через которые проходит цикл while, равно количеству элементов, через которые проходит цикл 2 for.

Другими словами, с for цикл, через который вы проходите (приблизительно) n-размерный куски n раз, и с циклом while вы проходите через n ^ 2-размерный кусок один раз.