Какова эффективность этой программы?

Question

Какова эффективность (в обозначении Big O) простой программы, которая пересекает двумерный массив целых и выдает каждый элемент.

В качестве примера возьмем следующий код:

public static void main(String args[])
{
   int[] array = {{1,2,3,4},
                  {5,6,7,8},
                  {9,10,11,12},
                  {13,14,15,16}};

    for(int i = 0; i < array.length; i++)
    {
       for(int j = 0; j < array[i].length; j++)
       {
          System.out.println(array[i][j]);
       }
    }
}

Answer 1

O (n * m) где n количество массивов (первое измерение) и m максимальный размер каждого внутреннего массива (второе измерение)

Answer 2

Я бы даже заметил, что размер м сравним с размером n и сделал бы это O (n ² ) .

Answer 3

Поскольку вы пересекаете каждый элемент в матрице один раз, это O (нм), где n - количество строк, а m - количество столбцов.

Answer 4

Учитывая, что ваш алгоритм посещает каждый элемент массива один раз, он равен O(n), где n - размер двумерного массива.

Answer 5

Потребуется O (n), потому что этот алгоритм займет то же время, если вы поместите одинаковое количество элементов в одномерный массив и выполните итерацию по нему в одном цикле.

Answer 6

Это O (n ^ 2), поскольку внутренний цикл зависит от внешнего цикла. O (n * m) редко описывает время выполнения циклов - это используется для графиков. Например: O (V + E) вершин и ребер.