第6章 变治法

三种变治法的类型

1.实例化简--同样问题

• 预排序
• 高斯消去法
• 平衡查找树--AVL树

2.改变表现--同样实例

• 2-3树
• 堆和堆排序
• 霍纳法则和二进制幂

3.问题化简--另一问题

---

预排序

• 3种基本的排序算法----选择排序、冒泡排序和插入排序
  效率：最坏情况下和平均情况下都是平方级的

• 2种高级算法----合并排序和快速排序
  效率：前者总是 O(nlog n)，后者在平均情况下也是 O(nlog n)，但最坏情况下是平方级

---

总结一下各排序算法

• 选择排序：
  简单选择排序算法通过n-i次关键字的比较，从n-i+1个记录种选出最小记录和第i（1<=i<=n）个记录交换。
  时间复杂度为：O(n^2)

• 冒泡排序：
  两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
  时间复杂度：O(n^2)

• 插入排序
  将一个记录插入到已经排好序的有序表种，从而得到一个新的、记录数增1的有序表。
  时间复杂度：O(n^2)

平均比较和移动次数约为 (n^2)/4，比冒泡和简单选择排序的性能要好一些。

• 合并排序
  对一个需要排序的数组一分为二，并对每个子数组递归排序，然后把这两个排好序的子数组合并为一个有序数组。
  需要将待排序列中的所有记录扫描一遍，因此耗费O(N)的时间，由完全二叉树深度可知，整个合并排序需要 logn(向上取整) 次。
  时间复杂度：O(nlog n)

• 快速排序
  通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
  时间复杂度：最优和平均情况下 O(nlog n)，最坏情况下（正序或逆序） O(n^2)
  空间复杂度：最好情况： O(logn)
  最坏情况：O(n)

---

二叉查找树

• 插入操作
• 删除操作
  1.叶子结点直接删除
  2.结点只包含左子树或者右子树
  直接删除该结点，并将其左子树或右子树设为其父结点的左子树或者右子树即可
  3.左右子树都不空，用其右子树的最小数据代替要删除的结点数据并递归删除该结点

在平均情况下，查找、插入和删除的效率为 O(log n)
最差情况下，退化成线性情况 O(n)

把一个集合变换称一棵二叉查找树是改变表现技术的一个实例

---

堆和堆排序

• 小顶堆
• 大顶堆

一棵完全二叉树，如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点 i/2（向下取整）。

堆排序

利用堆（假设为大顶堆）进行排序的方法。

基本思想：将待排序列构造成一个大顶堆，整个序列的最大值就是堆顶的根结点，将其与堆数组的末尾元素交换，此时末尾元素就是最大值，然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次大值。重复执行直到得到有序序列。

复杂度分析：主要是消耗在初始建堆和重建堆时的反复筛选上。最好最坏平均时间复杂度均为 O(nlog n)。

• 构建堆：完全二叉树最下层最右边的非终端结点开始构建，将它与其孩子进行比较和若有必要的交换（最多进行两次比较和互换操作），构建堆的时间复杂度为 O(n);
• 排序和重建堆：对长度为n的顺序表共需调用筛选算法n-1次，n个结点的完全二叉树深度为log n(向下取整) +1，重建堆的时间复杂度为 O(nlog n)。

T(n)=2T(n/2)+logn

记录的比较和交换是跳跃式进行的所以式一种不稳定算法。

• 结点的高度---该结点距离树叶的距离
• 结点的深度---该结点距离树根的距离

同一深度结点分布在树的同一层
同一高度结点可以分布在树的不同层

---

霍纳法则和二进制幂

霍纳法则

用一个两行的表，第一行包含了多项式的系数（如果存在等于0的系数也都包含进来），从最高的 a_n 到最低的 a₀ 。第二行中，除了第一个单元格用来存储 a_n ，其他单元格都将用来存储中间结果。做了这样的初始化之后，用第二行的最后一个单元格乘以x的值再加上第一行的下一个系数，来算出表格下一个单元格的值。

• 霍纳法则的有趣特性
  该算法在计算p(x)在某些点x₀上的值所产生的中间数字恰好可以作为p(x)除以x- x₀的商的系数，而算法的最后结果，除了等于p(x₀)以外，还等于这个除法的余数。

即，当x₀ =3时 p(x)=2x⁴-x³-3x²+x-5 除以 x-3 为2x³+5x²+18^x+55 和 160

• 效率分析：只要考虑一个n次多项式的第一项：a_nxⁿ，蛮力算法仅仅计算这一项就会需要n次乘法，霍纳法则除了计算这一项，还计算了其他 n-1 项，并且仍然只用了相同的乘法次数。

二进制幂

• 计算aⁿ

• 从左到右：累乘器初始化为a，从左到右扫描指数的位串，总是堆累乘器的最新值进行平方。而且，如果当前的二进制位为1，还要把存储变量乘以a。

• 从右到左：累乘器初始化为a，从右到左扫描指数的位串，只对前面项的计算结果进行平方来计算a²ⁱ，a²ⁱ=(a^2i-1)²，从最小值到最大值计算a的所有这样的乘方，但只把那些相应二进制位为1的项包括在累乘器中。

• 效率分析：每次重复它唯一循环时都要做一到两次乘法，计算aⁿ时，总的乘法次数M(n)是 (b-1)<M(n)<2(b-1) ，其中b是二进制位串的长度。(b-1)= (logn)向下取整，所以算法效率是对数级的。

---

问题化简

• 求最小公倍数问题
  简化为欧几里算法
• 计算图中的路径数量
  通过计算图的邻接矩阵的幂来计算两个顶尖之间路径数量的问题
• 简化为图的问题
• 线性规划