Какова пространственная сложность алгоритма, который возвращает список массивов?

Question

Я анализирую спиральную матрицу Алгоритм .Решение требует ввода матрицы и возврата списка массивов.Это выбранное решение:

class Solution {
public List < Integer > spiralOrder(int[][] matrix) {
    List ans = new ArrayList();
    if (matrix.length == 0)
        return ans;
    int r1 = 0, r2 = matrix.length - 1;
    int c1 = 0, c2 = matrix[0].length - 1;
    while (r1 <= r2 && c1 <= c2) {
        for (int c = c1; c <= c2; c++) ans.add(matrix[r1][c]);
        for (int r = r1 + 1; r <= r2; r++) ans.add(matrix[r][c2]);
        if (r1 < r2 && c1 < c2) {
            for (int c = c2 - 1; c > c1; c--) ans.add(matrix[r2][c]);
            for (int r = r2; r > r1; r--) ans.add(matrix[r][c1]);
        }
        r1++;
        r2--;
        c1++;
        c2--;
    }
    return ans;
}

}

Я искал сложность пространства на этом сайте , но я не знаю, как применить информацию к этому делу.

Я смотрел в разделе обсуждения комментариев.

Некоторые говорят, что это O (N) пространство, потому что решение создает список массивов.

Некоторые говорят, что это O (1) пробел, потому что вопрос требует возврата списка массивов.Так что это пространство уже учтено.

Какой из них верный?

Answer 1

Определенно O (n)

• Поскольку размер списка ans зависит от размера matrix, мы можемСкажите, что O(1) не ответ.Это потому, что O(1) обозначает постоянный пробел , что здесь не так.
• Список ans имеет точный размер n = width * height,что позволит ему содержать все элементы в matrix.
• Если наш matrix удвоится в размере, то наш ans также удвоится в размере, так как количество элементов удвоилось.Это указывает на линейное соотношение между размерами matrix и ans.Тогда мы можем сказать, что наше пространство - это сложность действительно O(n).

Answer 2

O (1) означает, что объем памяти, необходимый для этого алгоритма, не зависит от размера ввода.Это явно не так, элемент добавляется в список массивов каждый раз, когда выполняется один из внутренних циклов for.Таким образом, поскольку алгоритм имеет время выполнения O (MN), он также имеет сложность памяти O (MN), где матрица имеет размер M x N.