算法设计和的分析-分治法.ppt

有很大差异，分治算法的有效性很大程度上依赖于合并的实现。 public static int binarySearch(int [] a, int x, int n) { // 在 a[0] = a[1] = ... = a[n-1] 中搜索 x // 找到x时返回其在数组中的位置，否则返回-1 int left = 0; int right = n - 1; while (left = right) { int middle = (left + right)/2; if (x == a[middle]) return middle; if (x a[middle]) left = middle + 1; else right = middle - 1; } return -1; // 未找到x } 每执行一次算法的while循环， 待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn) 次。循环体内运算需要Θ(1) 时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn) 。 = 在密码系统与信息安全、数字信息、加密解密等领域，经常遇到大整数乘法的问题，通常的朴素算法需要Θ(n2)的运行时间。 一般地，我们可以采用分治法： X = Y = X = a 10n/2 + b Y = c 10n/2 + d XY = ac 10n + (ad+bc) 10n/2 + bd a b c d 复杂度分析 T(n)=Θ (n2) ?没有改进? 一个简单的例子： 23和14可以这样表示： 和 将它们相乘即 这个方法和朴素算法一样进行了4次乘法，并没提高效率。 改进： 为了降低时间复杂度，必须减少乘法的次数。 改进后可以表示为： XY = ac 10n + ((a-b)(d-c)+ac+bd) 10n/2 + bd 复杂度分析 T(n)= Θ(nlog3) = Θ(n1.59)?较大的改进? 问题：已知两个n?n的矩阵A和B，求它们的乘积，即C=A?B。 对于这个问题的计算公式为 显而易见由此设计的朴素算法时间复杂度为Θ(n3)。 考虑分治法能不能应用于矩阵乘法的的求解？ 将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为： 可得： 将原问题划分为8个同类型的子问题求解，可以提高算法的效率吗？ 复杂度分析 T(n)=O(n3) ?没有改进? 为了降低时间复杂度，必须减少乘法次数。 复杂度分析 T(n)=O(nlog7) =O(n2.81)?较大的改进? Hoare于1962年提出的，是对冒泡排序的改进。 算法思想(Divide and Conquer)： 取序列的一个元素作为轴，利用这个轴把序列分成两个子序列：左子序列和右子序列, 使得左子序列中各元素都小于等于轴，右子序列中各元素都大于等于轴。(分割原问题) 递归地处理两个子序列。（求解子问题） 注意：该算法最后无需合并子问题的解。 private static int partition (int[],int p, int r) { int i = p, j = r + 1; Comparable x = a[p]; // 将 x的元素交换到左边区域 // 将 x的元素交换到右边区域 while (true) { while (a[++i].compareTo(x) 0); while (a[--j].compareTo(x) 0); if (i = j) break; MyMath.swap(a, i, j); } a[p] = a[j]; a[j] = x; return j; } 38 65 97 76 13 27 49 i pivot = 49 0 1 2 3 4 5 6 j 49 38 97 76 13 i 49 38 27 76 65 j 49 38 27 13 76 97 65 i 13 38 27 76 97 65