时间复杂度
常数时间的操作：一个操作和数据量没关系 ，每次都是固定时间内完成的操作，叫做常数操作
时间复杂度：算法流程中常数操作数量的指标，在常数操作数量的表达式中，只要高阶项不要低阶项，去掉高阶项的系数，即O(f(N))
评价算法：先看时间复杂度指标，然后看实际运行时间，即常数项时间
时间复杂度举例：
举例
以上算法复杂度以此为O(MN)、O(M*logN)、O(M*logM)+O(M+N)
二分：不断对半分
外排：两个都有序，两个指针谁小移动谁
对数器
对数器的概念
准备二叉树，数组的随机样本发生器，以及对数器模板（甚至堆的模板，排序的模板）
冒泡排序（一般不用了）
每次冒泡出来一个最大的放后面，时间复杂度O(N^2)，额外空间复杂度O(1)，因为只需要额外几个变量就可以完成排序，如果是额外申请一个数组那么额外空间复杂度为O(N)
选择排序（一般不用了）
每次选最小的放前面，时间复杂度O(N^2)，额外空间复杂度O(1)
插入排序（类似扑克牌插牌）
先排0-1，再排0-2，...新来的数选合适的位置插入，直到全部排完，此时和数据状况有关系
最好情况：有序情况，O(N)
最差情况：逆序情况，O(N^2)
一律按最差的情况估计算法，所以时间复杂度O(N^2)，额外空间复杂度O(1)
递归
以数组中找最大值为例
例子
递归理解：系统帮你压栈，所以任何递归行为都可以改为非递归
压栈过程
估计复杂度的通式：T(N)=aT(N/b)+O(N^d)
通式
满足上述通式有直接得到时间复杂度的结论：
时间复杂度的结论
归并排序
先左侧排序，再右侧排序，最后用外排的方式统一（谁小就用谁并移动指针），T(N)=2T(N/2)+O(N)
时间复杂度O(N*logN)，额外空间复杂度O(N)
小和问题和逆序对问题
tips
①这样写防止溢出
②位运算比算术运算快
