1-时间复杂度和空间复杂度
为了找到最适合当前问题而估量“算法”的评价s
| 时间复杂度 | 空间复杂度 |
|---|---|
| 执行效率：根据算法编写出的程序，执行时间越短，效率就越高 | 占用的内存空间：不同算法编写出的程序，执行时占用的内存空间也不相同。如果实际场景中仅能使用少量的内存空间，就要优先选择占用空间最少的算法 |
时间复杂度（时间复杂度用来预估算法的执行时间）
时间复杂度计算的执行步骤：
- 统计算法中各个步骤的执行次数
- 简化算法的执行次数（类似数学中的“求导”）
- 用大 O 标记法表示算法的时间复杂度 O (频度)
常用的几种时间复杂度的比较：
O( 1 ) < O( log(n) ) < O( n ) < O( n^2 ) < O( n^3 ) < O( 2^n )
空间复杂度（空间复杂度用来估算一个算法执行时占用的内存大小）
空间复杂度计算的主要因素：
- 程序代码本身所占用的存储空间
- 如果需要输入输出数据，也会占用一定的存储空间
- 运行过程中，可能还需要临时申请更多的存储空间（这种影响比较大）
| 如果算法中额外申请的内存空间不受用户输入值的影响（是一个固定值），那么该算法的空间复杂度： | O(1) |
| 如果随着输入值 n 的增大，算法申请的存储空间成线性增长，则程序的空间复杂度是 | O(n) |
| 如果随着输入值 n 的增大，程序申请的存储空间成 n^2 关系增长，则程序的空间复杂度用 | O(n^2) |
| 如果随着输入值 n 的增大，程序申请的存储空间成 n^3 关系增长，则程序的空间复杂度用 | O(n^3) |
（多数场景中，挑选 “好” 算法往往更注重的是时间复杂度，空间复杂度只要处于一个合理的范围即可）