计算复杂度（Computational complexity）：用于研究解决特定问题X的算法效率的框架
计算模型（Model of computation）：可允许的操作（Allowable operations）
成本模型（Cost model）：操作数（Operation counts）
复杂度上界（Upper bound）：保证能在一定的时间内解决
复杂度下界（Lower bound）：通过数学方法证明，必须花费的最少时间
最优算法（Optimal algorithm）：可能达到的最小复杂度的算法（Algorithm with best possible cost guarantee for X），通常介于复杂度上界和下界之间
举例：排序
决策树模型：
有三个不同的元素a b c，通过比较的方式来得出排序结果。那么它的决策树为下图所示
树的高度代表了最差情况下需要比较的次数。
树的宽度代表了可能的排列顺序。
命题
任何基于比较的排序算法在最坏情况下至少要lg(N!) ~ N lgN 次比较。
证明
- 假设数组由N个不同的值组成，从a1到an
- 最坏情况由决策树的高度决定
- 二叉树最多可能的叶子节点数是2^h
- 因为数组有N!中不同的排序方式，所以至少有N!个叶子节点
结论
计算模型：决策树（decision tree）
成本模型：比较（compares）
上界：使用归并排序可以达到NlgN复杂度
下界：NlgN
最优算法：归并排序
归并算法的时间上界达到排序算法的时间下界；但耗费过多内存空间，从内存占用方面来讲并不是最优的。
影响排序复杂性的因素
- 输入的起始顺序
- 如果输入较为有序，则我们可能不需要NlgN次的比较（在数组完全有序的情况下，插入排序只要比较N-1次）
- 重复元素
- 如果输入带有重复元素，则我们可能不需要NlgN次的比较（使用3路快排（3-way quicksort））
- 元素的数字属性（Digital properties of keys）：我们可以用数字/特征比较（digit/character compares）来代替值比较（key compares）对数字和字符串进行比较
基于这些因素，可以根据数据的性质，来选择合适的排序算法。