📈1.1 大 O 表示法

一种随数据规模增长的变化趋势

复杂度也叫渐进复杂度，包括时间复杂度和空间复杂度。

（渐进）时间复杂度表示算法的执行时间与数据规模之间的增长关系。
（渐进）空间复杂度表示算法的存储空间与数据规模之间的增长关系。

asymptotic time complexity ~ 执行时间 ~ 更快 asymptotic space complexity ~ 存储空间 ~ 更省

大 O 复杂度表示法，表示的是代码的执行时间（或存储空间）随数据规模增长的变化趋势，而不是代码真正的执行时间（或存储空间）。

时间复杂度

T(n) = O(f(n))，其中，n 表示数据规模的大小， T(n) 表示所有代码的执行时间，f(n) 表示每行代码的执行次数之和。大 O 表示 T(n) 和 f(n) 成正比，即代码的执行时间和代码的执行次数成正比。

举个例子，假设每行代码的执行时间都一样，为 unitTime，那么：

$T(n) = (2n+2) * unitTime = O(2n+2) = O(n)$
$T(n) = (2n^2 + 2n + 3) * unitTime = O(2n^2 + 2n + 3) = O(n^2)$

通常我们会忽略掉公式中的常量、低阶、系数，只需要记录一个最大阶的量级就可以了，因为当 n 很大时，公式中的低阶/常量/系数并不左右增长趋势，所以都可以忽略。

复杂度量级

几种常见的复杂度量级（从低阶到高阶）如下：

分类

复杂度量级

大 O 表示

多项式量级

常量阶

O(1)

对数阶

O(logn)

线性阶

O(n)

线性对数阶

O(nlogn)

平方阶立方阶 k 次方阶

$O(n^2)$ $O(n^3)$ $O(n^k)$

非多项式量级

指数阶

O(2^n)

阶乘阶

O(n!)

O(1) 是常量级时间复杂度的一种表示方法，并不是表示只执行了一行代码。一般情况下，只要算法中不存在循环/递归语句，即使有成千上万行的代码，其时间复杂度也是 Ο(1)。大 O 这种复杂度表示方法只是表示一种变化趋势。

对数阶 O(logn) 和线性对数阶 O(nlogn)。不论对数的底是几都记为 O(logn)，因为换底公式可以提取任意常量。O(nlogn) 就是一段时间复杂度为 O(logn) 的代码循环了 n 遍。

非多项式量级的算法问题也叫 NP 问题，当数据规模 n 越来越大时，其执行时间会急剧增加/无限增长。

NP, Non-Deterministic Polynomial, 非确定多项式

多项式与非多项式

“多项式”是数学里的概念。维基百科-多项式：在数学中，多项式是由未知数（也称变量）和系数（也称常量）组成的表达式，它仅涉及到变量的加法、减法、乘法和非负整数幂运算。某个未知数 x 在多项式各项中的最大次数，称为多项式中 x 的次数，一个多项式的次数取决于幂次最高的那个。

比如 $x^2 - 4x + 7$ 是个一元（只有一个变量）二次（最高项是 $x^2$ ）多项式
比如 $x^4 + 2xyz^2 - yz + 1$ 是个三元（有三个变量）四次（最高项是 $x^4$ ）

所以，多项式量级就是指数据规模是多项式的。

如果数据规模是常数，此时多项式是个零元多项式（即都是常数项），用大 O 表示法就是 O(1)
如果数据规模是未知数 n，此时多项式是个一元一次多项式，用大 O 表示法就是 O(n^1) = O(n)
如果数据规模是未知数 n^2，此时多项式是个一元二次多项式，用大 O 表示法就是 O(n^2)
如果数据规模是未知数 n^3，此时多项式是个一元三次多项式，用大 O 表示法就是 O(n^3)
... 依次类推
如果数据规模是未知数 m 和 n，此时多项式是个二元一次多项式，用大 O 表示法就是 O(m+n)
... 依次类推

说明

总的时间复杂度就等于量级最大的那段代码的时间复杂度（加法法则）
嵌套代码的复杂度等于嵌套内外代码复杂度的乘积（乘法法则/嵌套循环）

注意：有的代码的复杂度是由多个数据规模来决定的，比如 O(m+n), O(m*n)，即多元X次多项式

空间复杂度

常见的空间复杂度有 O(1), O(n), O(n^2)。比如申请了一个变量、静态数组的长度、递归的深度（栈上消耗的空间）、动态 new 的空间（堆上消耗的空间）等等。

像 O(logn), O(nlogn) 这样的对数阶复杂度平时都用不到

例子

function add(n) {
    let sum = 0;
    for (let i = 1; i <= n; i++) {
        sum += i;
    }
    return sum;
}
// 时间复杂度 T(n) = (1+2n) * unit_time = O(1+2n) = O(n)
// 空间复杂度 O(1)

function add(n) {
    let sum = 0;
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= n; j++)
            sum += i * j;
    }
    return sum;
}
// 时间复杂度 T(n) = (1+n+2n^2) * unit_time = O(1+n+2n^2) = O(n^2)
// 空间复杂度 O(1)

let count = 0;
let i = 1;
while (i < n) {
    count++;
    i = i * 2;
}
// 时间复杂度 T(n) = O(log(n))
// 2^0, 2^1, 2^2, 2^3 ... 2^k ... (2^x = n)
// x = log2n

主要参考

https://time.geekbang.org/column/article/40036

Next1.2 不同情况

Last updated 3 years ago