分治算法基本原理和实践 分治算法详解及经典例题
一、基本概念在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)…… 任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。 例如,对于 n 个元素的排序问题,当 n=1 时,不需任何计算。n=2 时,只要作一次比较即可排好序。n=3 时只要作 3 次比较即可,…。而当 n 较大时,问题就不那么容易处理了。要想直接解决一个规模较大的问题,有时是相当困难的。 二、基本思想及策略分治法的设计思想是:将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。 分治策略是:对于一个规模为 n 的问题,若该问题可以容易地解决(比如说规模 n 较小)则直接解决,否则将其分解为 k 个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。 如果原问题可分割成 k 个子问题,1<k≤n,且这些子问题都可解并可利用这些子问题的解求出原问题的解,那么这种分治法就是可行的。 由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。 三、分治法适用的情况分治法所能解决的问题一般具有以下几个特征:
第一条特征是绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加; 第二条特征是应用分治法的前提它也是大多数问题可以满足的,此特征反映了递归思想的应用;、 第三条特征是关键,能否利用分治法完全取决于问题是否具有第三条特征,如果具备了第一条和第二条特征,而不具备第三条特征,则可以考虑用贪心法或动态规划法。 第四条特征涉及到分治法的效率,如果各子问题是不独立的则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然可用分治法,但一般用动态规划法较好。 四、可使用分治法求解的一些经典问题
?
五、分治法的基本步骤分治法在每一层递归上都有三个步骤:
它的一般的算法设计模式如下: Divide-and-Conquer(P) 1. if |P|≤n0 2. then return(ADHOC(P)) 3. 将P分解为较小的子问题 P1,P2,…,Pk 4. for i←1 to k 5. do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi 6. T ← MERGE(y1,y2,yk) △ 合并子问题 7. return(T) 其中 |P| 表示问题 P 的规模;n0 为一阈值,表示当问题 P 的规模不超过 n0 时,问题已容易直接解出,不必再继续分解。ADHOC(P) 是该分治法中的基本子算法,用于直接解小规模的问题P。 因此,当 P 的规模不超过 n0 时直接用算法 ADHOC(P) 求解。算法 MERGE(y1,yk) 是该分治法中的合并子算法,用于将 P 的子问题 P1,Pk 的相应的解 y1,y2,…,yk 合并为 P 的解。 六、依据分治法设计程序时的思维过程实际上就是类似于数学归纳法,找到解决本问题的求解方程公式,然后根据方程公式设计递归程序。
? 七、示例7.1 快速排序简述快速排序是一种排序执行效率很高的排序算法,它利用分治法来对待排序序列进行分治排序,它的思想主要是通过一趟排序将待排记录分隔成独立的两部分,其中的一部分比关键字小,后面一部分比关键字大,然后再对这前后的两部分分别采用这种方式进行排序,通过递归的运算最终达到整个序列有序,下面我们简单进行阐述。 快排思路我们从一个数组来逐步逐步说明快速排序的方法和思路。
快速排序之所以比较快,是因为相比冒泡排序,每次的交换都是跳跃式的,每次设置一个基准值,将小于基准值的都交换到左边,大于基准值的都交换到右边,这样不会像冒泡一样每次都只交换相邻的两个数,因此比较和交换的此数都变少了,速度自然更高。当然,也有可能出现最坏的情况,就是仍可能相邻的两个数进行交换。 快速排序基于分治思想,它的时间平均复杂度很容易计算得到为O(NlogN)。 代码实现/** * 快速排序 * @param array */ public static void quickSort(int[] array) { len; if(array == null || (len = array.length) == 0 || len == 1) { ; } sort(array,0,len - 1); } * 快排核心算法,递归实现 * array * left * right void sort(int[] array,int left,1)"> right) { if(left > right) { ; } // base中存放基准数 int base = array[left]; int i = left,j = right; while(i != j) { 顺序很重要,先从右边开始往左找,直到找到比base值小的数 while(array[j] >= base && i < j) { j--; } 再从左往右边找,直到找到比base值大的数 while(array[i] <= base && i < j) { i++ 上面的循环结束表示找到了位置或者(i>=j)了,交换两个数在数组中的位置 if(i < j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } } 将基准数放到中间的位置(基准数归位) array[left] = array[i]; array[i] = base; 递归,继续向基准的左右两边执行和上面同样的操作 i的索引处为上面已确定好的基准值的位置,无需再处理 sort(array,left,i - 1); sort(array,i + 1,right); } ?7.2?215. 数组中的第K个最大元素在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。 示例 1: 输入: [3,2,4] 和 k = 2
输出: 5
示例 2: 输入: [3,4,6] 和 k = 4
输出: 4
说明: 你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。 思路和算法我们可以用快速排序来解决这个问题,先对原数组排序,再返回倒数第 kk 个位置,这样平均时间复杂度是 O(n log n)O(nlogn),但其实我们可以做的更快。 在分解的过程当中,我们会对子数组进行划分,如果划分得到的 q 正好就是我们需要的下标,就直接返回 a[q];否则,如果 q 比目标下标小,就递归右子区间,否则递归左子区间。这样就可以把原来递归两个区间变成只递归一个区间,提高了时间效率。这就是「快速选择」算法。 我们知道快速排序的性能和「划分」出的子数组的长度密切相关。直观地理解如果每次规模为 n 的问题我们都划分成 1 和 n - 1,每次递归的时候又向 n?1 的集合中递归,这种情况是最坏的,时间代价是O(n ^ 2)O(n2)。 我们可以引入随机化来加速这个过程,它的时间代价的期望是 O(n),证明过程可以参考「《算法导论》9.2:期望为线性的选择算法」。 class Solution { int findKthLargest(int[] nums,1)"> k) { int len = nums.length; int targetIndex = len - k; int low = 0,high = len - 1; while (true) { int i = partition(nums,low,high); if (i == targetIndex) { nums[i]; } else if (i < targetIndex) { low = i + 1; } else { high = i - 1; } } } * 分区函数,将 arr[high] 作为 pivot 分区点 * i、j 两个指针,i 作为标记“已处理区间”和“未处理区间”的分界点,也即 i 左边的(low~i-1)都是“已处理区”。 * j 指针遍历数组,当 arr[j] 小于 pivot 时,就把 arr[j] 放到“已处理区间”的尾部,也即是 arr[i] 所在位置 * 因此 swap(arr,i,j) 然后 i 指针后移,i++ * 直到 j 遍历到数组末尾 arr[high],将 arr[i] 和 arr[high](pivot点) 进行交换,返回下标 i,就是分区点的下标。 */ private int partition(int[] arr,1)">int low,1)"> high) { low; int pivot = arr[high]; for (int j = low; j < high; j++if (arr[j] < pivot) { swap(arr,j); i++; } } swap(arr,high); i; } void swap(int i,1)"> arr[i]; arr[i] = arr[j]; arr[j] = tmp; } } 其实这段代码和快排很像,但是两者得目的是不一样的。 7.3?973. 最接近原点的 K 个点我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0,0) 最近的点。(这里,平面上两点之间的距离是欧几里德距离。) 你可以按任何顺序返回答案。除了点坐标的顺序之外,答案确保是唯一的。? 示例 1: 输入:points = [[1,3],[-2,2]],K = 1 输出:[[-2,2]] 解释: (1,3) 和原点之间的距离为 sqrt(10), (-2,2) 和原点之间的距离为 sqrt(8), 由于 sqrt(8) < sqrt(10),(-2,1)">) 离原点更近。 我们只需要距离原点最近的 K = 1 个点,所以答案就是 [[-2,2]]。 示例 2: 输入:points = [[3,[5,-1],4]],K = 2 输出:[[3,4]] (答案 [[-2,4],[3,3]] 也会被接受。) 思路我们想要一个复杂度比 N logN 更低的算法。 显然,做到这件事情的唯一办法就是利用题目中可以按照任何顺序返回 K 个点的条件,否则的话,必要的排序将会话费我们 N logN 的时间。 我们随机地选择一个元素 x = A[i] 然后将数组分为两部分: 一部分是到原点距离小于 x 的,另一部分是到原点距离大于等于 x 的。 这个快速选择的过程与快速排序中选择一个关键元素将数组分为两部分的过程类似。 如果我们快速选择一些关键元素,那么每次就可以将问题规模缩减为原来的一半,平均下来时间复杂度就是线性的。 算法 我们定义一个函数 work(i,j,K),它的功能是部分排序 (points[i],points[i+1],...,points[j]) 使得最小的 K 个元素出现在数组的首部,也就是 (i,i+1,i+K-1)。 首先,我们从数组中选择一个随机的元素作为关键元素,然后使用这个元素将数组分为上述的两部分。为了能使用线性时间的完成这件事,我们需要两个指针 i 与 j,然后将它们移动到放错了位置元素的地方,然后交换这些元素。 然后,我们就有了两个部分 [oi,i] 与 [i+1,oj],其中 (oi,oj) 是原来调用 work(i,K) 时候 (i,j) 的值。假设第一部分有 10 个元,第二部分有15 个元素。如果 K = 5 的话,我们只需要对第一部分调用 work(oi,5)。否则的话,假如说 K = 17,那么第一部分的 10 个元素应该都需要被选择,我们只需要对第二部分调用 work(i+1,oj,7) 就行了。 Solution { [][] points; int[][] kClosest(int[][] points,1)"> K) { this.points = points; work(0,points.length - 1return Arrays.copyOfRange(points,0void work(int j,1)">if (i >= j) int oi = i,oj = j; dist(ThreadLocalRandom.current().nextInt(i,j)); while (i <while (i < j && dist(i) < pivot) i++; while (i < j && dist(j) > pivot) j--; swap(i,j); } if (K <= i - oi + 1) work(oi,1)"> work(i+1,K - (i - oi + 1)); } int dist( i) { return points[i][0] * points[i][0] + points[i][1] * points[i][1]; } int t0 = points[i][0],t1 = points[i][1]; points[i][0] = points[j][0]; points[i][1] = points[j][1]; points[j][0] = t0; points[j][1] = t1; } } 可以发现的是,这道题目跟前面的还是很像的。 ? 参考文章分治算法详解及经典例题?? (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |