Какова правильная сложность времени?

Question

Я пишу алгоритм для преобразования * n матрицы в один массив.

1 2 3

4 5 6

7 8 9

= [1, 2, 3, 4, 5, 6, 7, 8, 9]

Я запутался, если то, что я сделал, это O (n ² ) или O(n ³ ):

public int[] mergeMatrix(int[][] matrix) {
    List<Integer> tempList = new ArrayList<>();
    for (int[] array : matrix) {
        for (int i : array) {
            tempList.add(i);
        }
    }
    int totalLength = tempList.size();
    int[] mergedArray = new int[totalLength];
    for (int i = 0; i < tempList.size(); i++) {
        mergedArray[i] = tempList.get(i);
    }
    return mergedArray;
}

Будет ли это O (n ² ), потому что это самый длинный наихудший случай процессов алгоритмов или O(n ³ ), потому что O (n) + O (n ² ) = O (n ³ )?

Answer 1

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

Причина этого:

• Вы выполняете ровно одну операцию для каждого элемента в итоговой матрице, который ограничен количеством строк и столбцов, которые у вас есть.

В контекстеиз n = m, тогда это будет O (n * n) или O (n ² ), но тогда только .

Число циклов не зависитэто действительно имеет значение здесь, так как вы могли бы делать невероятно необычные итерации с ним.Обязательно посмотрите на операции, которые вы фактически выполняете в цикле;поскольку они являются линейными, я ожидаю, что время выполнения будет линейным временем, умноженным на линейное время выполнения из-за вложенной природы.