## 常数操作 **一个操作 如果和数据量没有关系，每次都是固定时间内完成，叫做常数操作。** > 如做加减操作，数组寻址等。 ## 时间复杂度 **一个算法流程中，常数操作数量的指标** ## 空间复杂度 **一个算法流程中，多申请的内存空间的指标** > 如： 多开一个为n的辅助数组：O(n) 多开一个辅助的二维数组：O(n^2) 多开常数空间(如临时变量)：O(1) 注：递归调用是有空间代价的递归深度有多少 空间复杂度就有多少 ## 对数器  条件及元素： 1. 已知一个简单的绝对正确的算法A 2. 需要测试的算法B 3. 输入尽量随机，数据规模尽量大的样本 4. 如果A和B的输出结果一致，则能确定算法B也是正确的 ## master公式 递归的时间复杂度公式：`T(n) = a * T(n/b) + O(n^d) `   ## 快速排序 1.0：选最右边位置，小于或者等于的数放左边，大的放右边 2.0：选最右边位置，小于放左边，等于放中间，大于放右边（荷兰国旗问题） 3.0：随机选择位置，小于放左边，等于放中间，大于放右边（优化哨兵） ## 堆排序 ### 堆结构 堆是一颗完全二叉树。 大根堆：父节点大于孩子节点 小根堆：父节点小于孩子节点 如果用数组实现堆结构，则下标关系满足：（对于下标i位置） 父节点：`(i-1)/2` 左孩子：`2*i+1` 右孩子：`2*i+2` 堆操作： 入堆：heapInsert 堆化：heapify ### 排序 先将数组一次入堆，然后堆顶依次出堆，即可完成排序。 ## 比较器（Java内） 返回负数，第一个数排前面； 返回正数，第二个数排前面； ## 计数排序 统计次频count，按顺序一次打印，即可完成排序。  ## 基数排序 如果是十进制数排序，则用10个桶（是队列，先进先出）： 1. 先对个位数入桶，然后出桶 2. 再对十位数入桶，然后出桶 3. 再对百位数入桶，然后出桶 4. 依次类推，最后有序