递归与分治策略

递归 递归是一种解决问题的策略。给定一个问题，如果很容易知道： 如何把这个问题化简 如何解决最简单的特例 可以使用递归。

例子 --- 阶乘 Factorial(n) = Factorial(n - 1)*n Factorial(1) = 1 { if n==1 return 1; return n*Factorial(n-1); }

例子 --- Hanoi塔问题

例子 --- Hanoi塔问题 Hanoi(n, a, b, c) { if (n > 0) Hanoi(n-1, a, c, b); move(a,b); Hanoi(n-1, c, b, a); }

分治策略(Divide and Conquer) 用分治策略解决问题的基本思想： 分：把原问题分成一个或几个规模较小的子问题。 治：分别递归地解决被分割好的子问题。 合：合并子问题的结果，得到原问题的结果。

合并排序 合并排序的基本思想 分：把待排序的数组分成两个数组。 治：递归地分别对两个数组进行排序。 合：把两个已经排序好的数组合成一个数组并排序。

合并排序算法 mergeSort(A, p, r) { If p < r q = p + (r - p)/2; mergeSort(A, p, q); mergeSort(A, q+1, r); Merge(A, p, q, r); }

合并排序算法 mergeSort(A, p, r) { If p < r q = p + (r - p)/2; mergeSort(A, p, q); mergeSort(A, q+1, r); Merge(A, p, q, r); } 分 治 合

Merge Merge(A, p, q, r) n1 = q-p+1, n2 = r-q create arrays L[1..n1], R[1..n2] copy A[p..q] to L[1..n1], copy A[q+1..r] to R[1..n2] i = 1; j = 1; for k = p to r if L[i] < R[j] (assuming L[n1+1]=R[n2+1]=infinity) A[k] = L[i]; i = i + 1; else A[k] = R[j]; j = j + 1;

合并排序的复杂度 令T(n)为对n个数进行合并排序的复杂度。 T(n) = O(1) + 2T(n/2) + O(n) = 2T(n/2) + O(n) n>1 T(n) = O(1) n=1

递归树(recursion tree)

几种递归表达式的比较 递归表达式 复杂度 T(n) = T(n/2) + O(1) O(logn) T(n) = 2T(n/4) + O(n) O(n) T(n) = 2T(n/2) + O(n) O(nlogn) T(n) = 2T(n/2) + O(n2) O(n2)

快速排序 快速排序的基本思想是： 分：按照某个关键值把待排序的数组分成两个数组，使得第一个数组中的元素小于等于该关键值，第二个数组中的元素大于等于关键值。 治：递归地分别对两个数组进行排序。 合：把两个数组合成一个数组并排序。

快速排序 quickSort(A, p, r) { if p < r q = Partition(A, p, r); quickSort(A, p, q); quickSort(A, q+1, r); }

快速排序 quickSort(A, p, r) { if p < r q = Partition(A, p, r); quickSort(A, p, q); quickSort(A, q+1, r); } 分 治

Partition算法 i = p; j = r; while(i <= j) Partition(A, p, r) //将数组A[p..r]按某个关键值(pivot)分成两部分：A[p..j]和A[j+1..r]，使得A[p..j]中的元素都小于等于pivot； A[j+1..r]中的元素都大于等于pivot。 pivot = A[r]; i = p; j = r; while(i <= j) while(A[i] < pivot) i = i + 1; while(A[j] > pivot) j = j - 1; if(i <= j) swap(A[i], A[j]); i = i + 1; j = j - 1; return j;

快速排序的时间复杂性 令T(n)为对n个数进行快速排序的复杂度。 第1种情况： T(n) = T(1) + T(n - 1) + O(n) 第2种情况： T(n) = 2T(n/2) + O(n) (T(n) = O(nlogn))

快速排序的时间复杂性 快速排序算法的复杂度依赖于关键值(pivot)的选取。 如果每次选取的关键值恰好是数组中的最大(最小)元素，就会产生极不均匀的分割，导致算法复杂度较高 --- O(n2)。 如果每次选取的关键值恰好是数组的中间元素（一半元素大于该关键值，一般元素小于该关键值。），则会产生均匀的分割，这样算法的复杂度较低 --- O(nlogn)。

快速排序的时间复杂性 令T(n)为对n个数进行快速排序的复杂度。 最坏情况： T(n) = T(1) + T(n - 1) + O(n) 最好情况： T(n) = 2T(n/2) + O(n) (T(n) = O(nlogn)) 平均情况： T(n) = O(nlogn)

随机化的快速排序算法

为什么要在快速排序算法中引入随机性？

引入随机性的原因 假设在某次程序比赛中，你和你的对手都各自编写了一个快速排序程序。 比赛规则：源代码公开，对手之间互相提供测试样例。 对手用的算法：我们前面讲过的快速排序算法（pivot值为数组中最后一个元素的值）。 问题：你给你的对手提供什么样的测试样例？

引入随机性的原因 其它条件相同，假设在对手的算法中： pivot值为数组中处在中间位置的元素的值，是否存在测试样例使得对手算法的复杂度为Θ(n2)？ 对于任何pivot值的选取方式，是否都存在测试样例使得对手算法的复杂度为Θ(n2)？

作业 小明设计了一个快速排序算法vulnerableSort，并将算法公开。你的任务是生成一些输入，使得vulnerableSort的效率最低。vulnerableSort算法和quickSort算法(参看课件)类似，唯一的区别在于pivot值的选取。 1) 假设在vulnerableSort 中，pivot值的选取方式为：“q = p + 0.5*(r - p); pivot = A[q];”。请你给出一个长度为7的数组作为vulnerableSort算法的输入，使得vulnerableSort的效率最低。 2) 假设在vulnerableSort 中，pivot值的选取方式为：“q = p + α*(r - p); pivot = A[q]; (α为某个固定值)”。请你设计一个算法，给定任意一个α(0≤α≤1)和任意一个自然数n，该算法能自动生成一个数组B[1..n]作为vulnerableSort算法的输入，使得vulnerableSort的效率为Θ(n2)。

“q = p + α*(r - p); pivot = A[q];” 引入随机性的原因 结论 若pivot值的选取方式为： “q = p + α*(r - p); pivot = A[q];” 对任何确定的α，都存在某些输入，使得算法在该输入下时间复杂度为Θ(n2)。 解决办法 为了应对对手可能的“攻击”，要将α变成一个随机值，从而将快速排序算法随机化。

随机化的快速排序算法 RandomizedQuickSort(A, p, r) { if p < r q = RandomizedPartition(A, p, r); quickSort(A, p, q); quickSort(A, q+1, r); }

RandomizedPartition算法 RandomizedPartition(A, p, r) a = rand(0, 1); q = p + a * (r - p); pivot = A[q]; i = p; j = r; while(i <= j) while(A[i] < pivot) i = i + 1; while(A[j] > pivot) j = j - 1; if(i <= j) swap(A[i], A[j]); i = i + 1; j = j - 1; return j;

类似的“攻击” 2003年，有人曾经对linux内核进行了一次攻击．该攻击针对内核中用到的一种数据结构：哈希表（hash table）． 在理想情况下，哈希表中“查找，插入，删除”的复杂度都是O(1)．该攻击通过生成“恶意数据”的方法使得，所有操作复杂度为O(n)．

随机算法的作用之一：降低对输入数据随机性的依赖 随机性的快速 排序算法： 带有一种 内置的随机性 (built-in randomness) 确定性的快速 排序算法 依赖于输入 数据的 “随机性” 不依赖输入 数据的 “随机性”

分治策略(Divide and Conquer) 用分治策略解决问题的基本思想： 分：把原问题分成若干个子问题。 治：分别递归地解决子问题。 合：合并子问题的结果。

合并排序算法 mergeSort(A, p, r) { If p < r q = p + (r - p)/2; mergeSort(A, p, q); mergeSort(A, q+1, r); Merge(A, p, q, r); } 对A[p..r]排序 分 治 合

快速排序 quickSort(A, p, r) { if p < r q = Partition(A, p, r); quickSort(A, p, q); quickSort(A, q+1, r); } 分 治

为什么合并排序和快速排序算法的效率高？ 分治策略适用于什么样的问题？

求n个数和的问题（反例） 已知数组A[1..n]，求数组当中n个数的和。 例如， 输入： 输出：44 3 2 5 11 8 10 4 1

算法1 Sum(A[1..n]) result = 0; for i = 1 to n result = result + A[i]; return result; 复杂度O(n)

基于分治策略的方法 思想： 3 2 5 11 8 10 4 1 目标：求数组的和。 策略： 1. 将数组分为两部分。 2. 分别递归地求出两部分的和。 3. 把两个部分和相加，得到总和。 + + + 3 2 5 11 8 10 4 1

算法2 recursiveSum(A[p..r]) if (p == r) return A[p]; else mid = p + (r - p)/2; firstHalf = recursiveSum(A[p..mid]); secondHalf = recursiveSum(A[mid+1..r]); return firstHalf + secondHalf; 如果求A[1..n]中所有元素的和，则调用recursiveSum(A[1..n])。 分 治 合

算法2 --- 复杂度 T(n) = 2T(n/2) + O(1), n > 1 T(1) = O(1), n = 1 

比较 算法1： 从头到尾按顺序求n个数的和。 3 2 5 11 8 10 4 1

比较 算法2： “分治策略”只是利用加法的结合率，改变了求和的次序，并未减少求和的次数。 + + + 3 2 5 11 8 10 4 1

求最大最小值问题 给定一个数组A[1..n]，求数组中的最大元素和最小元素。 例如，对于下面的数组，其最大值和最小值分别为11和1。 3 2 5 11 8 10 4 1

算法1 Maxmin(A[1..n]) max = A[1]; min = A[1]; for i = 2 to n if A[i] > max max = A[i]; if A[i] < min min = A[i]; return (max, min); 复杂度T(n) = 2n – 2

算法2 思想： 目标：求一个数组的最大值和最小值。 3 2 5 11 8 10 4 1 策略： 1. 将数组分为两部分。 2. 分别求出两部分的最大值和最小值。 3. 合并两部分结果。 (11,1) (11,2) (10,1) 3 2 5 11 8 10 4 1

算法2 Maxmin(A[p..r]) if (r – p == 0) return (A[p], A[r]); if (A[p] < A[r]) return (A[r], A[p]); else return (A[p], A[r]); else mid = p + (r - p)/2; (firstmax, firstmin) = Maxmin(A[p..mid]); (secondmax, secondmin) = Maxmin(A[mid+1..r]); if (firstmax > secondmax) max = firstmax; else max = secondmax; if (firstmin < secondmin) min = firstmin; else min = secondmin; return (max, min); 分 治 和

算法2 --- 复杂度 T(n) = 2T(n/2) + 2, n > 2 T(n) = 1, n = 2  T(n) = 3n/2 – 2

比较 算法1复杂度2n – 2 算法2复杂度3n/2 – 2 算法2比算法1少进行了n/2次比较

一个数的n次幂 输入：a, n(n为自然数) 输出：a的n次幂 例如， 输入：3, 4（求3的4次幂） 输出：81

算法1 Power(a, n) result = 1; for i = 1 to n result = result * a; return result; 复杂度O(n)

算法2 思想： an = a 如果n = 1 = an/2*an/2 如果n是偶数 = an/2*an/2*a 如果n是奇数,n≠1 作业 根据以上思想写出计算a的n次幂的算法Power(a, n)。分析该算法的复杂度(以n为参数)，即该算法执行了多少次乘法运算。

思考题 定义：c为一个数组A[1..n]的“大多数元素(majority element)”当且仅当c在数组A中出现次数大于n/2。 问题：给定一个数组A[1..n]，设计算法，求数组A的大多数元素c（若c存在）。 (1) 要求算法的复杂度为O(nlogn)。 (2) 要求算法的复杂度为O(n)。