如何评价算法复杂度
常数操作
常数操作：执行时间固定和数据量没有关系的运算操作，如果和数据量有关就不是常数操作。
- ±*/运算
- 数组寻址（数组里获取3位置和3000w位置数据时间相等）
1+1 和100w+100w时间是固定的，花费时间差不多。
linkedlist的寻址就不是常数操作，地址跳跃，需要遍历来获取目标。
时间复杂度
时间复杂度：描述发生N次常数操作的指标。
- 将算法过程分解到常数级别操作。
- 将得到的表达式，仅保留高阶项，忽略低阶和常数操作。
- 选择数据最差的场景来估算时间复杂度。O()就代表最差情况的复杂度。
额外空间复杂度
除了数据本身占用的空间，需要申请多少额外的空间来完成算法。估算时，每个数占用的空间为O(1)。列：插入中你自己使用了一个新的数组用来作为临时内存保存结果，空间复杂度就是O(N).
- i,j等遍历的参数不算额外空间
- 如果用户要求生成一个新的数组，也不算额外空间。
如何比较常数操作的优劣
直接跑几千万次，对比不同常数操作看哪个消耗时间短的就好。
例如：对比乘法和位操作，可以发现位操作比较节省时间。所以位运算比普通运算好。
什么是最优解
- 首先保证时间复杂度是最低的
- 尽可能保证额外空间复杂度最低。注：能不用额外内存，就不要用。
最优解不考虑常数操作，只比较最高次项。
冒泡排序 O(N^2)
S_n = na_1 + \frac{n(n-1)}{2}d = {\frac{n^2}{2}} -\frac{(1-2a1)}{2}n
不关心低阶项目，也不关心系数，表达式中最高阶就是复杂度。冒泡排序时间复杂度即为N^2
N趋于无穷大时，系数项和低阶项都可以忽略不计。讨论的是数据量和运行时间关系。
| 复杂度 |
说明 |
| O(1) |
常数操作 |
| O(logN) |
二分法 |
| O(N) |
单次遍历 |
| O(N*logN) |
|
| O(N^2) |
冒泡、插入排序 |
| O(N^k) |
|
| O(2^n) |
|
| O(K^n) |
|
| O(n!) |
N的阶乘，最低效的 |
