第4章 减治法

减治法

• 基本思想：将规模为n的问题递减为规模为n-1(减常数)或n/2（减因子）的子问题,反复递减后对子问题求解,再建立子问题的解与原问题的解的关系。
  （减常数、减因子或减可变规模）

• 减常量
  1.插入排序
  2.拓扑排序
  3.生成组合对象的算法

• 减因子、减可变规模
  1.减常因子算法
  2.减可变规模算法

---

插入排序

• 直接插入排序
  与已有序的元素依次一一比较， 确定位置后再实施插入。
  基本操作：比较
  最坏情形：严格递减数组，每次插入需比较已插入的所有元素，第i次插入比较i个元素，n(n-1)/2 ∈ Θ(n²)
  最优情形：升序排列，每次插入只需比较一次，n-1 ∈ Θ(n)。
  平均效率：对无序元素，n²/4 ∈ Θ(n²)
• 折半二分查找/插入
  基本操作：比较
  最坏情形：W(n)=W(n/2)（向下取整） + 1
  W(1)=1，设 n=2k，可解得 W(n)= k+1 = log n + 1
  通解 W(n) = log n +1， W(n)∈Θ(log n)
  平均复杂度： C(n)= log n +1/2

基本排序最差情况比较：

• 直接插入排序 最差Θ(n²)
  最优 Θ(n) 遇到基本有序数组表现优异性能，可结合快速排序
  平均 Θ(n²)
• 合并排序 最差Θ(nlog n)
• 快速排序 最差Θ(n²)
  最优Θ(nlog n)
  平均Θ(1.38nlogn)
• 选择排序 Θ(n²)
• 冒泡排序 Θ(n²)

拓扑排序

对给定的有向无环图，要求按照某种顺序列出它的顶点序列，使图的每一条边的起点总在结束顶点之前。

在余下的有向图中求出一个源，它是一个没有输入边的顶点，然后把它和所有从它出发的边都删除。（如果有多个这样的源，可以任意选一个。如果这样的源不存在，算法停止该问题无解。）顶点被删除的次序就是拓扑排序问题的一个解。

---

减常因子法

• 假币问题
  有n个金币，其中一个是假币。这个假币的重量比真币的重量要轻一点，所有n-1个金币的重量是一样的。现在你有一架天平，设计高效的算法（用最少的使用天平次数）找出那个假的金币。
  1.用减治法(减半）
  把n个硬币分为两堆，每堆(n/2)(向下取整)个，每次称一堆。
  复杂度对应的递推式
  易见 W(1)=0
  W(n)=W(n/2)(向下取整)+1
  解得 W(n)= log₂n
  2.用减治法(减n/3）
  把n个硬币分为三堆，每堆(n/3)(向下取整)个，每次称任意二堆。
  易见 W(1)=0
  W(n)=W(n/3)(向下取整)+a
  解得 W(n)= log₃n

---

减可变规模算法

• 计算中值和选择问题
  1.选择问题：
  求一个n数组的第k个最小元素。
  一些特殊的情况
  k=1
  k=n
  k=(n/2)(向下取整)，该元素被称为中值(第(n/2)(向下取整)个元素)
  2.使用快速排序中的分区算法
  效率分析
  平均情况下：
  和快速排序比要高效
  严格的数学分析表明，平均情况下的效率和每次都消减一半情况下的效率是完全相同的。
  每次都消减一半的递推式是
  C(n)=C(n/2)+(n-1) ----- Θ(n)
  对一个n元素数组进行划分总是要n-1次键值比较。如果不需要更多迭代就能得到分割位置而使问题得解，在这种最好情况下n-1 ∈ Θ(n)
  最坏情况复杂度----- Θ(n2)

• 插值查找(在有序数组中)
  查找时考虑key的特点，找一个更加准确位置的元素值进行比较，以便更快确定是否在数组里。
  算法思想：
  设某次迭代处理的是数组最左边元素A[l]和最右边元素A[r]之间的部分，要查找的键值为v。
  建立通过 点(l,A[l])和点(r,A[r])的 直线方程，取y=v，求出横坐标x，比较A[x]与v的值，决定是停止，还是在l与x-l之间或x+l与r之间继续查找。

关于折半查找和插值查找的说明

1.对于小的文件折半查找可能更好一些；
2.对于更大的文件和那些访问成本非常高的的应用，插值查找更值得考虑；
3.平均来说插值查找的键值比较次数log₂log₂n + 1。