算法分析与设计AlgoDALectureNotesW5章节.pptVIP

Last Section Divide and Conquer MINMAX: 2n – 2 vs. 3n/2 – 2 二分有哪些信誉好的足球投注网站: 算法BINARYSEARCHREC在n 个元素组成的已排序数组中有哪些信誉好的足球投注网站某个元素所执行的元素比较次数不超过 ； 非递归； 合并排序： nlogn 寻找第 k 小元素：20cn 划分算法与快速排序：n-1 Divide and Conquer 大整数乘法： n log 3 ≈ n1.59 矩阵乘法与STRASSEN 算法：nlog7 ≈ n2.81 最近点对：nlgn 凸包：nlgn，n2 最近点对 T(n)=1 若n=2 =3 若n=3 =2T(n/2)+ Θ(n) 若n3 Θ(nlgn) Code 最近点对 T(n)=1 若n=2 =3 若n=3 =2T(n/2)+ Θ(n) 若n3 Θ(nlgn) 蛮力 DC 凸包（快包） Average: Θ(nlgn) Worst: Θ(n^2) Brute Force 根据(x1,y1), (x2,y2)的直线方程 (y2-y1)x+(x1-x2)y=(x1y2-y1x2) n(n-1)/2, n-2, n3 Decrease and Conquer 减 治 减 治 减治技术利用了一种关系： 一个问题给定实例的解和同样问题较小实例的解之间的关系。 一旦建立了这样一种关系，我们既可以递归地，也可以非递归地地来运用减治技术。 减治法有３种主要的变种： 减去一个常量 (decrease by a constant) 减去一个常数因子(decrease by a constant factor) 减去的规模是可变的(variable size decrease) Decrease by a constant 在减常量变种中，每次算法迭代总是从实例规模中减去一个规模相同的常量。经常地，这个常量等于一。 函数f(n) = an可以用一递归定义来计算 f(n) =　f (n-1) *a 如果n 1 = a 如果n = 1 *和蛮力法是一样的效率？ 得出这个做法的思想过程是不同的 Decrease by a constant factor 减常因子技术意味着在算法的每次迭代中，总是从实例的规模中减去一个相同的常数因子。在多数应用中，这样的常数因子等于二。 计算an的值是规模为n的实例； 规模减半（常数因子等于二）的实例计算就是an/2 的值； 它们之间有着明显的关系： an = (an/2)2。 Decrease by a constant factor an = (an/2)2 n是偶数 = (a(n-1)/2)2 a n是大于１的奇数 = a n = 1 上式递归根据所做的乘法次数来度量效率，该算法属于O (log n); 因为,每次迭代的时候，以不超过两次乘法为代价，问题的规模至少会减小一半。 Decrease by a constant factor 该算法和基于分治思想的算法有所不同: 分治算法对两个规模为n/2的指数问题实例分别求解： an =　 如果n1 = a 如果n = 1 O(n) Variable size decrease 在减治法的减可变规模变种中，算法在每次迭代时，规模减小的模式都是不同的。 欧几里德算法： gcd (m,n) = gcd (n, m mod n) 欧几里德算法 Euclid (m,n) While n≠0 do r← m mod n m ← n n ← r return m m 和 n既不是以常数，也不是以常数因子的方式减小 插入排序 用减一技术来对一个数组A[0…n-1]排序 假设对较小数组A[0…n-2]排序的问题已经解决了，我们得到了一个大小为n-1的有序数组：A[0]≤…≤A [n-2]。 我们如何把这个较小规模的解和元素A[n-1]一同考虑， 来得到原问题的解呢？ 显然，我们所要做的就是在这些有序的元素中为A[n-1]找到一个合适的位置， 然后把它插入到那里。 插入排序 InsertionSort(A[0…n-1]) //输入：n个可排序元素构成的一个数组A[0…n-1] //输出：非降序排序的数组A[0…n-1] for i ← 1 to n-1 do w ← A[i] j ← i-1 While j ≥ 0 and A[j] w do A[j+1] ← A[j] j ← j-1 A[j+1] ← w 插入排序 最坏输入是一个严格递减的数组