三种变治法的类型
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的系数也都包含进来），从最高的 an 到最低的 a0 。第二行中，除了第一个单元格用来存储 an ，其他单元格都将用来存储中间结果。做了这样的初始化之后，用第二行的最后一个单元格乘以x的值再加上第一行的下一个系数，来算出表格下一个单元格的值。
- 霍纳法则的有趣特性
该算法在计算p(x)在某些点x0上的值所产生的中间数字恰好可以作为p(x)除以x- x0的商的系数，而算法的最后结果，除了等于p(x0)以外，还等于这个除法的余数。
即，当x0 =3时 p(x)=2x4-x3-3x2+x-5 除以 x-3 为2x3+5x2+18x+55 和 160
- 效率分析：只要考虑一个n次多项式的第一项：anxn，蛮力算法仅仅计算这一项就会需要n次乘法，霍纳法则除了计算这一项，还计算了其他 n-1 项，并且仍然只用了相同的乘法次数。
二进制幂
-
计算an
-
从左到右：累乘器初始化为a，从左到右扫描指数的位串，总是堆累乘器的最新值进行平方。而且，如果当前的二进制位为1，还要把存储变量乘以a。
-
从右到左：累乘器初始化为a，从右到左扫描指数的位串，只对前面项的计算结果进行平方来计算a2i，a2i=(a2i-1)2，从最小值到最大值计算a的所有这样的乘方，但只把那些相应二进制位为1的项包括在累乘器中。
-
效率分析：每次重复它唯一循环时都要做一到两次乘法，计算an时，总的乘法次数M(n)是 (b-1)<M(n)<2(b-1) ，其中b是二进制位串的长度。(b-1)= (logn)向下取整，所以算法效率是对数级的。
问题化简
- 求最小公倍数问题
简化为欧几里算法 - 计算图中的路径数量
通过计算图的邻接矩阵的幂来计算两个顶尖之间路径数量的问题 - 简化为图的问题
- 线性规划
网友评论