2010-2011-2《算法分析》ppt-5变治法

《2010-2011-2《算法分析》ppt-5变治法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、变治法基本思想变换！（1）把问题的实例变得更容易求解。（2）对实例进行求解。主要类型：（1）实例简化（2）改变表现（3）问题转化预排序在问题求解之前，先进行排序，然后在求解问题。例1检验数组中元素的唯一性（1）蛮力法，扫描统计，O(n2)（2）先排序，再扫描统计，O(nlogn)预排序例2模式统计在一个给定的序列中找到出现次数最多的一个模式。比如：英文单词（1）蛮力法，扫描统计，O(n2)（2）先排序，再扫描统计，O(nlogn)预排序例3查找问题：在一个数组中是否存在某个给定的数。（1）蛮力法，O(n)（2）先

2、排序，后查找，排序：O(nlogn)，查找：O(log2n)合计：O(nlogn)高斯消去法二元联立方程：a11x+a12y=b1a21x+a22y=b2a11x+a12y=b1(a21x+a22y)*(a11/a21)=b2*(a11/a21)a11x+a12y=b1a11x+(a22*a11/a21)y=b2*(a11/a21)高斯消去法一般的n个方程的n元联立方程组：a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2……an1x1+an2x2+…+annxn=bn高斯消

3、去法a’11x1+a’12x2+…+a’1nxn=b’1a’22x2+…+a’2nxn=b’2……a’nnxn=b’n高斯消去法初等变换：（1）交换方程组中两个方程的位置（2）把一个方程替换为它的非零倍。（3）把一个方程替换为它和另一个方程倍数之间的和或差。举例：p156高斯消去法GaussElimination(A[1…n,1…n],b[1…n]){forj=1tonA[j,n+1]=b[j]fori=1ton-1forj=i+1tonfork=iton+1A[j,k]=A[j,k]-A[I,k]*A[j,i]

4、/A[i,I]}高斯消去法上面代码的问题：（1）可能有系数是0（2）最内的循环存在重复计算现象，效率低。（3）误差累计，有除法，计算机只能表示小数点后面的有限位数BetterGaussElimination(A[1…n,1…n],b[1..n]){fori=1tonA[i,n+1]=b[i]fori=1ton-1pivotrow=iforj=i+1tonif

5、A[j,i]

6、>

7、A[pivotrow,i]

8、pivotrow=jfork=iton+1swap(A[i,k],A[pivotrow,k])forj=i+1

9、tontemp=A[i,k]/A[i,i]fork=iton+1A[j,k]=A[j,k]-A[i,k]*temp}高斯消去法时间复杂度：O(n3)其他应用：（1）LU分解（2）计算矩阵的逆（3）计算矩阵的行列式平衡查找树AVL树：G.M.Adelson-Velsky和E.M.Landis定义：一棵AVL树是一棵二叉查找树，其中每个节点的平衡因子定义为该节点左子树和右子树的高度差，这个平衡因子要么是0，要么是+1，或者-1P163AVL树的调整（1）右单转（2）左单转（3）左右双转（4）右左双转P164排序分析排

10、序！排序的时间复杂度分析排序的最好复杂度为什么是：O(nlogn)?有3个互不相等元素组成的序列：k1，k2，k3对此3个元素进行排序，唯一的方法是两两进行比较。比较的结果两种：大于，小于。排序的时间复杂度分析两两比较结果，形成一颗比较二叉树，二叉树的高度就是比较的次数。排序的时间复杂度分析因为k1，k2，k3互不相等，它们之间只可能有下列6种关系：①k1

11、复杂度分析二叉树的性质：叶子数量（记为U）和树高度(记为H)的关系。H>=[log2U]就是说：有U个叶子的二叉树至少有H高度。而比较二叉数的叶子数为:N!所以它的高度至少是:[log2N!]排序的时间复杂度分析建立一个模型：即有一个含有m=n!个元素的集合A，甲从中任取一个，让乙来猜，但允许乙提出k个“是”或“非”问题。问在最坏情况下k应该是多少？乙提出第1个“是”或“非”问题，可将集合A分为A1（1）和A2（1）两个子集合，其中必有一个集合（设为A1（1）），它包含的元素个数（用∣A1（1）∣来表示）不少于，

12、即∣A1（1）∣≥m/2排序的时间复杂度分析若甲所取的元素正好在A1（1），乙提出第2个“是”或“非”问题后将集合A1（1）分为A2（1）和A2（2），其中之一设为A2（1）有∣A1（2）∣≥∣A1（1）∣≥m/22依此类推有∣A1（k）∣≥m/2kk必须足够大，使得m/2k≤1排序的时间复杂度分析则已可在最坏情况下通过k次提问题找到所要寻找的元素，即猜到A取得元素，这里