1.快速排序

• 基于比较的排序方法，最好的算法不会好于$O(nlog(n))$，因为比较搜索树中$2^n \ge nlogn$;

2. 堆排序

• 建堆复杂度为O(n)，（使用错位相减法求等比数列与等差数列乘积的数列和）

  设堆中有n个元素, 对应完全二叉树有k层(2k-1≤n＜2k)，第i层向下调整移动距离最大为(k-i), 第i层节点数为2i-1总移动次数： $2*\sum_{i=1}^{k-1}*(k-i) = O(n)$

3.大整数乘法

4.矩阵乘法

5.快速排序

​ 比较排序可以被抽象为一颗决策树。决策树是一颗完全二叉树，他可以表示在给定输入规模的情况下，某一特定算法对所有元素的比较操作。

• 基于比较的排序方法，最好的算法不会好于$O(nlogn)$ 因为比较搜索树中$2^h>=n!$,从而$h>=nlogn$

6.第k小元素