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

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

原文：http://www.cnblogs.com/Jimtastic/p/4003517.html