数据结构与算法之美 - 学习笔记
时间复杂度
算法中的语句执行次数称为语句频度或时间频度，记为 T(n)。算法的时间复杂度也就是算法的时间度量，记作 T(n) = O(f(n))。表示随问题规模 n 的增大，算法执行时间的增长率和 f(n)的增长率相同
大 O 时间复杂度表示法
算法的执行效率，粗略的讲就是算法代码的执行时间
举例
假设每行代码的执行时间都为 unit_time，估算以下代码执行时间
int cal(int n) {
int sum = 0; // 1 unit_time
int i = 1; // 1 unit_time
for (; i <= n; ++i) { // n unit_time
sum = sum + i; // n unit_time
}
return sum;
}
总执行时间为 T(n) = (2n+2)*unit_time
int cal(int n) {
int sum = 0; // 1 unit_time
int i = 1; // 1 unit_time
int j = 1; // 1 unit_time
for (; i <= n; ++i) { // n unit_time
j = 1; // n unit_time
for (; j <= n; ++j) { // 循环嵌套 n^2 unit_time
sum = sum + i * j; // n^2 unit_time
}
}
}
总执行时间为 T(n) = (3+2n+2n^2)*unit_time
推导大 O
T(n) = O(f(n))
T(n)表示代码的执行时间；n 表示数据规模的大小；f(n)表示每行代码执行的次数总和，因为这是一个公式，所以用 f(n)来表示。公式中的 O，表示代码的执行时间 T(n)与 f(n)表达式成正比
大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫做渐进时间复杂度，简称时间复杂度
当 n 很大时。公式中的低阶、常量、系数不左右增长趋势可忽略。只需记录一个最大量级即可
拿第二段代码举例: 第二段代码中 T(n) = O(2n^2+2n+3). 在此公式中, 低阶是 2n , 常量是 3 , 系数是 2. 这三部分都不会左右增长趋势,所以可以忽略，就可记为 T(n)=O(n^2)
时间复杂度分析（实用方法）
1. 只关注循环执行次数最多的一段代码
大 O 这种复杂度表示方法只是表示一种变化趋势，忽略公式中常量、低阶、系数，只记录一个最大阶的量级即可
2. 加法法则：总复杂度等于量级最大的那段代码的复杂度
如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n)))
量级最大也就是项的次数最高
3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)T2(n)=O(f(n))O(g(n))=O(f(n)*g(n)).
几种常见时间复杂度实例分析
复杂度量级（按数量级递增）
[图片上传失败...(image-57f5d4-1626169860582)]
NP 问题：时间复杂度为非多项式量级的算法问题
当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法（O(2^n)和 O(n!)）
1. 常数阶 O(1) :表示该算法的执行时间总是为一个常量
// 不论输入的数据集是大是小，只要没有循环等复杂结构，这个代码的时间复杂度就是常数阶
val i = 1;
var j = 2;
var k = i + j;
2. 线性阶 O(n) :表示一个算法的性能会随着输入数据的大小变化而线性变化
// 循环执行次数随输入n变化
for (var i = 0; i < n; i++) {
console.log(i);
}
3. 平方阶 O(n^2) ：表示一个算法的性能会随着输入数据的增长而呈现二次增长，常见为对输入数据进行嵌套循环
// 若不断嵌套，算法性能将会变为O(n^k)
for (var i = 0; i < n; i++) {
for (var j = 0; j < n; j++) {
console.log(j);
}
}
4. 指数阶 O(2^n) :算法性能随输入数据每次增加而增大两倍(斐波那契数列)
5. 对数阶 O(logn)
// 在while循环里面，每次都将 i 乘以 2，直到i不小于n退出
// 假设循环次数为x，也就是说 2 的 x 次方等于 n
// 则由2^x=n得出x=log₂n。因此这个代码的时间复杂度为$O(logn)$
var i = 1;
while (i < n) {
i = i * 2;
}
6. 线性对数阶 O(nlogn) :将时间复杂度为对数阶 O(logn)的代码循环 n 遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了 O(nlogn)
常见算法时间复杂度由小到大
Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n²)＜Ο(n³)＜…＜Ο(2n)＜Ο(n!)<O(nn)
[图片上传失败...(image-9277f1-1626169860582)]
Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是 Ο(1)。
Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n ^ 2)和 Ο(n ^ 3)称为多项式时间，而 Ο(2n)和 Ο(n!)称为指数时间。前者是有效算法，把这类问题称为 P 类问题，而把后者称为 NP 问题
空间复杂度分析
空间复杂度全称为渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系
时间复杂度还分为：最好/坏情况时间复杂度、平均情况时间复杂度、均摊时间复杂度。根据具体情况分析
