复杂度分析

首发于：2021-02-18

学习数据结构和算法之前必须要学会复杂度分析，复杂度分析是整个算法学习的精髓，只要掌握了它，数据结构和算法的内容基本上就掌握了一半

时间复杂度分析

时间复杂度代表代码执行时间随数据规模增长的变化趋势。

7种常见时间复杂度

• O(1) 常数时间复杂度
• O(n) 线性时间复杂度
• O(n²) 指数时间复杂度
• O(log n) 对数时间复杂度
• O(k^n) n次方时间复杂度
• O(n log n) 线性对数时间复杂度
• O(n!) 阶乘时间复杂度

时间复杂度比较

O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(k^n) < O(n!)

计算方法案例

例1：计算 1 + 2 + 3 + ... + n

方法1：从1到n的循环累加

let sum = 0
for (let i = 1; i < n; i++) {
    sum += i
}

时间复杂度 O(n)

方法2：求和公式 sum = n(n+1)/2

const sum = n * (n + 1) / 2

时间复杂度 O(1)

例2：递归，求斐波拉契数列的值，Fib：0, 1, 1, 2, 3, 5, 8, 13, 21, ...

F(n) = F(n - 1) + F(n - 2)

直接使用递归，时间复杂度 O(2^n)

function fib(n) {
    if (n < 2) {
        return n
    }
    return fib(n - 1) + fib(n - 2)
}

主定理求递归时间复杂度：

二分查找： T(n) = T(n/2) + O(1) => O(log n)

二叉树：T(n) = 2T(n/2) + O(1) => O(n)

排好序的二维矩阵二分查找：T(n) = 2T(n/2) + O(log n) => O(n)

归并排序：T(n) = 2T(n/2) + O(n) => O(n log n)

空间复杂度分析

空间复杂度代表算法的存储空间与数据规模之间的增长关系。

我们常见的空间复杂度就是 O(1)、O(n)、O(n^2 )，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。

如果开一个数组，数组的长度就是空间复杂度，一维数组 O(n)，二维数组 O(n^2)。