算法的衡量

算法的复杂性体现在运行该算法时占用计算机资源的多少上，计算机最重要的资源是时间（CPU）和空间（内存），因此复杂度分为时间和空间复杂度

• 时间复杂度 T(n) —— 根据算法写成的程序在执行时耗费时间的长度

• 空间复杂度 S(n) ——根据算法写成的程序在执行时占用存储单元的长度

1. 时间复杂度

定义：在进行算法分析时，语句总的执行次数 T(n) 是关于问题规模 n 的函数，进而分析 T(n) 随 n 的变化情况并确定 T(n) 的数量级，即算法运行时间随着数据量变大时的增长趋势

1.1 函数渐近上界

设算法 计算操作数量 为 T(n) ，其是一个关于输入数据大小 n 的函数

例如，某算法的操作数量为 T(n) = 3 + 2n，T(n) 是个一次函数，说明时间增长趋势是线性的，因此易得时间复杂度是线性阶，我们将线性阶的时间复杂度记为 O(n)，这个数学符号被称为 大O记号，代表函数 T(n) 的 渐近上界

我们要推算时间复杂度，本质上是在计算 操作数量函数 T(n) 的渐近上界 本质上看，计算 渐近上界 就是在找一个函数 f(n) ，使得在 n 趋向于无穷大时，T(n) 和 f(n) 处于相同的增长级别（仅相差一个常数项 c 的倍数）

1.2 推算大O阶的方法

推算出 f(n) 后，我们就得到时间复杂度 O(f(n)) 首先 统计操作数量，然后 判断渐近上界 即可确定渐近上界 f(n)

1.2.1 统计操作数量

对着代码，从上到下一行一行地计数即可。操作数量 T(n) 中的各种系数、常数项都可以被忽略。根据此原则，可以总结出以下计数技巧：

1. 跳过数量与 n 无关的操作。因为他们都是 T(n) 中的常数项，对时间复杂度不产生影响
2. 省略所有系数。例如，循环 2n次、5n+1 次、……，都可以化简记为 n 次，因为 n 前面的系数对时间复杂度也不产生影响
3. 循环嵌套时使用乘法。总操作数量等于外层循环和内层循环操作数量之积，每一层循环依然可以分别套用上述 1. 和 2. 技巧

根据以下示例，使用上述技巧得到的统计结果为 T (n) = $n^2$ + n

let a = 1 // +0（技巧 1）
a = a + n // +0（技巧 1）
// +n（技巧 2）
for(let i=0;i<5*n+1;i++){
    console.log(0)
}
// +n*n（技巧 3）
for(let i=0;i<2*n;i++){
    for(let j=0;j<n+1;j++){
        console.log(0)
    }
}

1.2.2 判断渐近上界

时间复杂度由多项式 T(n) 中最高阶的项来决定。这是因为在 n 趋于无穷大时，最高阶的项将处于主导作用，其它项的影响都可以被忽略

因此上述例子推出的时间复杂度结果为 O($n^2$)

1.3 常见类型

时间复杂度按数量级递增顺序为：

常数阶 O (1)<对数阶 O ($\log n$ )<线性阶 O (n)<线性对数阶 O ($n\log n$ )<平方阶 O ($n^2$)<立方阶 O ($n^3$)<k 次方阶 O ($n^k$)<指数阶 O ($2^n$)<O (n!)<O ($n^n$)

2. 空间复杂度

常见的空间复杂度有O(1)、O(n) 和 O($n^2$)