returns 数组列表的算法的 space 复杂度是多少？

Question

我正在分析螺旋矩阵 algorithm。该解决方案要求输入矩阵和数组列表的 return。这是选择的解决方案：

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;
}

}

我已经查看了 space 复杂性 site 但我不知道如何将这些信息应用到这个案例中。

我看了评论的讨论部分。

有人说它是 O(N) space 因为解决方案创建了一个数组列表。

有人说是O(1)space因为这题需要数组列表的return。这样space已经算进去了。

哪个是真的？

Answer 1

O(1) 意味着此算法所需的内存量不依赖于输入的大小。这显然不是这种情况，每次内部 for 循环之一迭代时，都会将一个元素添加到数组列表中。因此，由于该算法具有 O(MN) 运行时间，它也具有 O(MN) 内存复杂度，其中矩阵的大小为 M x N.

Answer 2

绝对是 O(n)

由于 Listans 的 大小取决于 matrix 的大小，我们可以说 O(1) 不是答案。这是因为O(1)表示一个常量space，这里不是
列表 ans 的确切大小为 n = width * height，这将允许它包含 matrix 中的所有项目。
如果我们的 matrix 大小增加一倍，那么我们的 ans 大小也会增加一倍，因为项目数量增加了一倍。这表明 matrix 和 ans 的大小之间存在 线性关系。然后我们可以说我们的 space 复杂度确实是 O(n).

returns 数组列表的算法的 space 复杂度是多少？

What is the space complexity of an algorithm that returns an array list?

java

algorithm

big-o

space-complexity

data-structures

绝对是 O(n)