常用算法之分治法

18 sec read

分治法概念

分治法(divide-and-conquer)字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。分治有两个特点:

  1. 子问题相互独立且与原问题形式相同
  2. 反复分治,使划分得到的子问题小到不能再分时,直接对其求解

分治法所能解决的问题一般具有以下特征:

  1. 该问题的规模缩小到一定程度就可以容易的解决。
  2. 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构的性质。
  3. 利用该问题分解出的子问题的解可以合并为该问题的解(关键性质)
  4. 该问题所分解出的各个子问题最好是相互独立的,即子问题之间不包含公共的子问题。

其中:

  • 第一条特征是绝大多数问题都能满足的,因为计算复杂性一般随着规模的减小而降低。
  • 第二条特征是应用分治法的前提,它也是大多数问题可以满足的,此特征反映了递归思想的应用。
  • 第三条特征是关键,能否利用分治法完全取决于问题是否具有第三条特征。如果具备了第一条特征和第二条特征,而子问题的解不可以合并,则可以考虑贪心算法或动态规划。
  • 第四条特征涉及分治法的效率,如果各子问题不是独立的,则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然可用分治法,但一般用动态规划法较好。

分治模式在每一层递归上都有三个步骤:

  • 分解(Divide):将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。
  • 解决(Conquer):若子问题规模较小而容易求解则直接求解,否则递归的解决各个子问题。
  • 合并(Combine):将各个子问题的解合并为原问题的解。

分治法的一般算法框架如下:

分治法求解的一些经典问题:

  • 二分搜索
  • 大整数乘法
  • Strassen矩阵乘法
  • 棋盘覆盖
  • 合并排序
  • 快速排序
  • 线性时间选择
  • 最接近点对问题
  • 循环赛日程表
  • 汉诺塔

分治法的典型实例

二分搜索

问题描述:给定已按照升序排列好的n个元素 a[0:n-1],现在要在这n个元素中找出一特定元素。

问题分析:采用分治法的思想,充分利用元素之间已经存在的次序关系,将序列划分为两个个数相同的左右两个部分,取最中间的元素和x进行比较,如果等于中间的元素就找到,如果不等于,就递归的在左边(x<中间值)或者右边(x>中间值)二分查找。

注意事项:对于二分查找,一般需要建立两个不变性:

  • 当前待查找序列,肯定包含目标元素
  • 每次待查找序列的规模都会变小。

Python示例:

快速排序

快速排序(Quicksort),是一种排序算法,最坏情况复杂度:Ο(n2),最优时间复杂度:Ο(n log n),平均时间复杂度:Ο(n log n)。快速排序的基本思想也是用了分治法的思想:找出一个元素X,在一趟排序中,使X左边的数都比X小,X右边的数都比X要大。然后再分别对X左边的数组和X右边的数组进行排序,直到数组不能分割为止。

快速排序的基本思想:设当前待排序的无序区为R[low..high],利用分治法可将快速排序的基本思想描述为:

  • 分解:在R[low..high]中任选一个记录作为基准(Pivot),以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high],并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字key,右边的子区间中所有记录的关键字均大于等于pivot.key,而基准记录pivot则位于正确的位置(pivotpos)上,它无须参加后续的排序。(注意:划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(注意pivot=R[pivotpos]):R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys,其中low≤pivotpos≤high。)
  • 求解:通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
  • 组合:因为当”求解”步骤中的两个递归调用结束时,其左、右两个子区间已有序。对快速排序而言,”组合”步骤无须做什么,可看作是空操作。

Python实现:

打赏作者
微信支付标点符 wechat qrcode
支付宝标点符 alipay qrcode

《怕蛇的人怎么学Python》:开篇

先前在自己的博客上,零散的写了一些Python的学习笔记,涉及到的内容比较凌乱,完全没有逻辑。反思自己对所学的
3 sec read

Hive SQL中的datediff、current_dat…

Hive SQL中的datediff函数返回的是2个日期的天数。在使用过程中发现了一个比较有趣的坑: SELE
2 min read

使用Python进行相关性分析

在数据分析时,经常会针对两个变量进行相关性分析。在Python中主要用到的方法是pandas中的corr()方
42 sec read

发表评论

电子邮件地址不会被公开。 必填项已用*标注