接收nxn二维数组的函数初始化(n-2)x(n-2)数组的空间复杂度疑问

我在解决一道LeetCode题目时，需要确定一个接收n×n二维数组的函数的空间复杂度，该函数内部会初始化一个(n-2)×(n-2)大小的新二维数组。

代码实现 #

/**
 * @param {number[][]} grid
 * @return {number[][]} 
 */
var largestLocal = function(grid) {
    // declare (n-2 x n-2) matrix
    const matrix = new Array(grid.length - 2).fill(0)
                  .map(() => new Array(grid[0].length - 2).fill(0));

    for (let i = 0; i < grid[i].length - 2 ; i++) {
        for(let j = 0; j < grid.length - 2 ; j++) {
            // find the max in each 3x3 matrix
            matrix[i][j] = Math.max( 
                grid[i][j],     grid[i][j+1],   grid[i][j+2],
                grid[i+1][j],   grid[i+1][j+1], grid[i+1][j+2],
                grid[i+2][j],   grid[i+2][j+1], grid[i+2][j+2]
            );
        }
    }

    return matrix;
};

我的困惑 #

我现在困惑的是，该函数的空间复杂度应视为O(n)（因为和输入规模层级相同）还是O(n²)？我猜测是O(n)，但不确定。

[1] 空间复杂度：描述算法所需内存（空间）与输入规模关系的函数，通常指所需的“额外”内存，不包含存储输入本身所需的内存。

解答 #

该函数的空间复杂度是O(n²)，理由如下：

• 空间复杂度计算的是算法额外开辟的内存空间量级，这里核心关注新创建的matrix数组：它的大小为(n-2)×(n-2)，展开后元素总数是n² - 4n + 4。
• 根据大O表示法的规则，我们只保留最高阶项并忽略常数项和低阶项，因此这个数组的空间量级为O(n²)。
• 你猜测的O(n)对应线性空间（比如一维数组元素数量与n成正比），但这里二维数组的元素总数和n的平方成正比，不属于线性空间范畴。

内容的提问来源于stack exchange，提问作者Hasan S.