算法的空间复杂度

? ? ? ? 在此之前，务必对算法的时间复杂度有所了解。
????????

一、名词解释

????????在计算机科学中，一个算法或程序的空间复杂度定性地描述该算法或程序运行所需要的存储空间大小。空间复杂度是相应计算问题的输入值的长度的函数，它表示一个算法完全执行所需要的存储空间大小。（不明白可跳过，最后再细读）

????????和时间复杂度类似，空间复杂度通常也使用大O记号来渐进地表示。就像时间复杂度的计算不考虑算法所使用的空间大小一样，空间复杂度也不考虑算法运行需要的时间长短。

二、常用分类

????????算法的空间复杂度是指算法在执行过程中所需的存储空间大小与输入规模之间的关系。它用来描述算法对内存使用的需求，通常以大O表示法表示。

空间复杂度的计算包括算法执行过程中占用的额外空间，不仅仅是输入数据的存储空间，还包括算法内部使用的辅助空间。空间复杂度可以分为以下几种情况：

????????1.O(1)（常数空间复杂度）： 算法所需的额外空间是一个常数，与输入规模无关。这意味着不随着输入数据的增加而增加额外的存储空间。以下是一些示例：

????????交换变量：

????????这个交换变量的例子中只使用了一个额外的变量 temp，无论输入的数据是什么规模，都只需要常数级别的额外空间。

function swap(a, b) {
    let temp = a;
    a = b;
    b = temp;
}

????????递增计数器：

? ? ? ??这个例子中的计数器只需要一个常数级别的空间，不论执行多少次。

function incrementCounter() {
    let counter = 0;
    counter++;
}

????????固定大小的数组：

????????在这个例子中，无论输入数组的大小如何，额外的存储空间都是常数级别的。

function constantArrayOperation(arr) {
    const fixedSizeArray = new Array(5);
    // 对固定大小的数组进行一些操作
}

????????常数大小的变量：

????????在这个例子中，常数大小的变量占用的额外空间是固定的。

function constantVariables() {
    const constantVar1 = 10;
    const constantVar2 = "constant";
}

????????2.O(n)（线性空间复杂度）： 算法所需的额外空间与输入规模成线性关系。例如，需要一个与输入规模相等的数组来存储数据。

????????数组的复制：

????????这个例子中，新数组 newArr 的大小与输入数组 arr 的大小成线性关系，因此具有线性空间复杂度。

function copyArray(arr) {
    let newArr = new Array(arr.length);
    for (let i = 0; i < arr.length; i++) {
        newArr[i] = arr[i];
    }
}

????????字符串拼接：

function concatenateStrings(strArray) {
    let result = "";
    for (let i = 0; i < strArray.length; i++) {
        result += strArray[i];
    }
}

????????递归调用：

????????在这个递归函数中，每次调用都会占用一定的栈空间，调用次数与输入参数 n成线性关系，因此具有线性空间复杂度。

function recursiveFunction(n) {
    if (n <= 0) {
        return;
    }
    recursiveFunction(n - 1);
}

????????3.O(n^2)、O(n^3) 等（多项式空间复杂度）： 空间复杂度与输入规模的幂次关系成正比。例如，某些嵌套循环算法可能需要二维数组，导致空间复杂度为 O(n^2)。

????????4.O(log n)、O(sqrt(n)) 等（对数空间复杂度）： 空间复杂度与输入规模的对数关系成正比。例如，一些分治算法的递归调用可能导致对数级别的空间复杂度。

????????5.O(2^n)、O(n!) 等（指数空间复杂度）： 空间复杂度与指数级别或阶乘级别的关系。通常这类算法的空间需求非常大，不适用于大规模问题。

三、总结

????????算法（Algorithm）是指用来操作数据、解决程序问题的一组方法。对于同一个问题，使用不同的算法，也许最终得到的结果是一样的，但在过程中消耗的资源和时间却会有很大的区别。

那么我们应该如何去衡量不同算法之间的优劣呢？

主要还是从算法所占用的「时间」和「空间」两个维度去考量。

• 时间维度：是指执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述。
• 空间维度：是指执行当前算法需要占用多少内存空间，我们通常用「空间复杂度」来描述。

因此，评价一个算法的效率主要是看它的时间复杂度和空间复杂度情况。然而，有的时候时间和空间却又是「鱼和熊掌」，不可兼得的，那么我们就需要从中去取一个平衡点。

? ? ? ? 前文所述，既然时间复杂度不是用来计算程序具体耗时的，那么我也应该明白，空间复杂度也不是用来计算程序实际占用的空间的。空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势。

四、进阶

? ? ? ? 冒泡排序与插入排序的空间复杂度分别是多少？

????????冒泡排序：

function bubbleSort(arr) {
    const n = arr.length;

    for (let i = 0; i < n - 1; i++) {
        for (let j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }

    return arr;
}

冒泡排序的空间复杂度是 O(1)。这是因为冒泡排序算法在排序过程中只使用了常数级别的额外空间，主要是用于交换元素的临时变量。随着输入规模的增加，额外空间的使用并不会线性增长，因此其空间复杂度是恒定的。

????????二维数组的存储

function createMatrix(n) {
    const matrix = [];

    for (let i = 0; i < n; i++) {
        matrix[i] = [];
        for (let j = 0; j < n; j++) {
            matrix[i][j] = 0; // 或者其他初始值
        }
    }

    return matrix;
}

二维数组 matrix 的大小为 n x n，占用了 O(n^2) 的空间。

????????矩阵运算

function matrixMultiplication(matrix1, matrix2) {
    const rows1 = matrix1.length;
    const cols1 = matrix1[0].length;
    const rows2 = matrix2.length;
    const cols2 = matrix2[0].length;

    if (cols1 !== rows2) {
        throw new Error("Invalid matrix dimensions for multiplication");
    }

    const result = createMatrix(rows1, cols2);

    for (let i = 0; i < rows1; i++) {
        for (let j = 0; j < cols2; j++) {
            for (let k = 0; k < cols1; k++) {
                result[i][j] += matrix1[i][k] * matrix2[k][j];
            }
        }
    }

    return result;
}