计算复杂度（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）

举例：排序

计算模型：决策树（decision tree）

　　　　　决策树的高度决定了耗费的时间

成本模型：比较（compares）

上界：归并排序是NlgN

下界：NlgN

最优算法：归并排序（MergeSort的时间上界达到排序算法的时间下界；但MergeSort耗费过多内存空间）

影响排序复杂性的因素

• 输入的起始顺序
  
  • 如果输入较为有序，则我们可能不需要NlgN次的比较（在序列有序的情况下，插入排序只要比较N-1次）
• 重复元素
  • 如果输入带有重复元素，则我们可能不需要NlgN次的比较（3路快排（3-way quicksort））
• 元素的数字属性（Digital properties of keys）：我们可以用数字/特征比较（digit/character compares）来代替值比较（key compares）对数字和字符串进行比较　　　　　　　

普林斯顿大学算法课 Algorithm Part I Week 3 排序算法复杂度 Sorting Complexity