美文网首页
算法(3)-分治法

算法(3)-分治法

作者: tianyl | 来源:发表于2019-03-05 22:22 被阅读0次

分治法

定义

在计算机科学中,分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。
这个技巧是很多高效算法的基础,如排序算法(快速排序、归并排序)、傅立叶变换(快速傅立叶变换)。

分治算法是一个解决复杂问题的好工具,它可以把问题分解成若干个子问题,把子问题逐个解决,再组合到一起形成大问题的答案。比如,汉诺塔问题如果采用分治算法,可以把高度为n的塔的问题转换成高度为n-1的塔来解决,如此重复,直至问题化简到可以很容易的处理为止

步骤

分治法的实现一般分为三步:
分解:将原问题分解为若干个规模较小,相对独立,与原问题形式相同的子问题。
解决:若子问题规模较小且易于解决时,则直接解。否则,递归地解决各子问题。
合并:将各子问题的解合并为原问题的解

适用范围

  1. 该问题的规模缩小到一定的程度就可以容易地解决
  2. 该问题可以分解为若干个规模较小的相同问题
  3. 利用该问题分解出的子问题的解可以合并为该问题的解
  4. 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题(如果不满足此条件,虽然可以用分治法,但是不推荐)

应用

分治法有很多地方的应用,比较常见的有二分查找或者排序算法就是使用的分治法的思想

二分查找

二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。 但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。所以对于链式存储结构,二分查找效率是较为低下的,不建议使用

二分查找的思想也较为简单,就是讲n个元素分为两个部分,然后与需要查找的元素进行比较,如果比要查找的元素小,则在大的元素集合中查找,如果比要查找的元素大,则在较小的元素集合中查找,具体代码如下

  • 非递归
public static int binarySearch(int[] array,int fromIndex,int toIndex,int key){
        int low=fromIndex;
        int high=toIndex-1;
        while(low<=high){
            int mid=(low+high)/2;
            int midVal=array[mid];
            if(key>midVal){
                low=mid+1;
            }else if(key<midVal){
                high=mid-1;
            }else{
                return mid;
            }
        }
        return -(low+1);
    }
  • 递归
public static int binarySearch(int srcArray[], int start, int end, int key) {
        int mid = (end + start) / 2;
        if (srcArray[mid] == key) {
            return mid;
        }
        if (start < end) {
            if (key > srcArray[mid]) {
                return binarySearch(srcArray, mid + 1, end, key);
            } else if (key < srcArray[mid]) {
                return binarySearch(srcArray, start, mid - 1, key);
            }
        }
        return -1;
    }

排序

在排序算法中,使用分治法思想的排序有快速排序和归并排序

快速排序

设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用数组的第一个数)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序,然后不断重复这个过程直到排序完成

归并排序

归并排序是一个典型分治法思想的排序,它的思想是,如果两个序列是有序的,那么将它们合成,依然可以得到一个有序序列,而对于一个无需的序列,将它拆分为足够小的序列然后进行排序,最后将这些有序序列合并,那么就可以得到一个有序的序列

对于这两个排序的详细步骤和代码,这里只做简介,之后放在排序章节里统一描述

相关文章

  • 算法(3)-分治法

    分治法 定义 在计算机科学中,分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”,就是把...

  • Divide and Conquer

    算法之 分治法 Divide and Conquer 分治法: 分治法的设计思想是:将一个难以直接解决的大问题,分...

  • 分治法,动态规划及贪心算法区别

    原文:分治法,动态规划及贪心算法区别 1.分治法 分治法(divide-and-conquer):将原问题划分成n...

  • 3.1 分治法介绍及关键点解析

    Chapter3: 更好的查找与排序算法 1. 分治法介绍及关键点解析 什么是分治法 基本思想 将原问题划分为若干...

  • [算法导论]归并排序

    时间复杂度 《算法导论》2.3.1 分治法。 归并排序采用了分治法的递归排序。分治法:分解子问题,解决子问题,合并...

  • 归并排序

    1、分治法 归并排序是完全遵循分治策略的排序算法。什么是分治法? 分治法,即将原问题分解为几个规模较小的子问题,递...

  • 一、基础算法分析类型

    常见的算法分析类型如下: 1、分治法 2、动态规划法 3、回溯法 4、分支限界法 5、贪心法

  • 算法导论第2.3章 - 分治算法

    分治算法 递归:算法一次或多次递归地调用其自身已解决紧密相关的若干子问题。这些算法遵循分治法的思想。 分治算法三个...

  • Divide and Conquer

    算法学习之分治法(divide and conquer)

  • [小撒学算法]分治法与合并排序

    小撒是一只好学的小鸭子,这天,小撒在学习算法 分治法 分治法(divide-and-conquer)是一种算法设计...

网友评论

      本文标题:算法(3)-分治法

      本文链接:https://www.haomeiwen.com/subject/vhbauqtx.html