时间复杂度

1. 忽略常数时间的操作
2. 确定算法总操作数和样本数量之间的表达式关系
3. 只看表达式最高阶部分

如一个选择排序算法，每次都要遍历 n-1-n 个数查找出当前子数组中最小值做交换，0~n-1、1~n-1、・・・，而交换最小值到当前下标 index 为常数操作每次固定时间，遍历操作为等差数列和公式 化简为$a{N}^2\ast bN+c$，只看最高阶为 2 次方，粗略估计为$O(N^2)$

常见的常数操作:

• 算术运算
• 位运算
• 赋值、比较、自增、自减等
• 数组寻址

固定时间为常数操作，时间不固定则不是常数操作

如果某个算法流程的复杂程度会根据数据状况不同而不同，那么必须按照最差情况估计

如插入排序 在最差的情况下 数组中每个数都要进行交换

在插入排序中，当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较 N- 1 次，时间复杂度为 $O(N)$

最坏的情况是待排序数组是逆序的，此时需要比较次数最多，总次数记为：1+2+3+…+N-1，所以，插入排序最坏情况下的时间复杂度为$O(N^2)$