算法导论系列:分治算法

说起分治法,大家一定也都听过秦始皇采用郡县制将国家分为三十六郡的故事,我们常说”山高皇帝远”,意思就是山高路远,皇帝都管不了,实际上无论皇帝多远,山有多高,整个国家都属于朝廷统治,但皇帝一个人是管不了这么多事情的,那如何一统天下?秦始皇的郡县制其实就是分而治之的一种变种,我们现在的国家也是这样,国家分省,市,县,乡,这样层次管理,无论在那个偏僻的角落,都不是无政府的.

而我们的分治法,其实是一种很古老的策略,<孙子兵法>里有句古话,”凡治众如治寡,分数是也”,这里的”分数”,是指分到各层次的部分,”数”是指每部分人的人数,意思就是将帅只需要通过管理少数几个人即可实现管理全部队的各个组织,这样,人数众多的军队,就如同管理几个人一样容易.在算法设计中,我们也引入分而治之的策略,称为分治算法,其本质其实就是将一个问题分解为若干个规模较小的相同子问题,分而治之.

分治算法秘籍:

分治法解题的基本步骤如下:

1:分解问题:

将要解决的问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题

2:问题治理:

求解各个子问题,由于各个子问题和原问题的形式相同,只是规模较小,因此当子问题划分的足够小时,我们就可以用较为简单的方法去解决.

3:问题合并

按照原问题的要求,将子问题的解逐层的合并构成原问题的解.

一句话总结,分治法就是将一个难以直接解决的大问题,分割成规模较小的相同子问题,以便各个击破,分而治之.

在使用分治法时,使用递归算法是解决问题的利器.下面我们用二分搜索,这个最典型的分治问题来举例,看看分治算法是如何进行工作的.

二分搜索-猜数问题

我们一定都玩过猜数游戏,现在我们两个人玩这个游戏,我在我的手心写一个100以内的整数,并且只能给你大了或小了的提示,并且只有三次机会,那如何才能以最快的速度猜出来呢?

解题思路:

从问题的描述来看,如果是n个数,最坏的情况我们得猜n次才可以成功,其实我们没有必要非得一个个的去猜,这显然是一个笨方法,因为这些数是有序的,我们可以按照折半查找的方式,每次和中间的元素去比较,如果每次比中间的部分大,去后半部分找,比中间部分小,去后半部分找.

那我们现在思路有了,可以将问题抽象描述出来:

给定n个元素,假设这些元素是有序的,从中查找特定元素x.

解题思想:

将有序序列先大致分为数目相等的两组,然后去中间的元素与特定的查找元素进行比较,如果x等于中间元素,查找成功,如果x小于中间元素,在前半部分继续执行分解和治理操作,如果x大于中间元素,去后半部分进行分解和治理.

算法设计:

使用一维数组S[]放置该有序序列,设置变量low和high表示查找的上下界,middle表示中间的位置,x为特定的查找元素.

1:初始化.令low=0(S[]中的第一位数),high=n-1(S[]中最后一位数).

2:middle = (low+high)/2,表示中间的查找范围.

3:判断low<high是否成立,如果成立,继续下一步,否则结束.

4:判断x与S[middle]的关系,如果两者相同,算法结束,输出结果,否则,如果x>S[middle],low = middle+1,如果x<S[middle],则high = middle-1.

实战演练:

实验结果:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏chenjx85的技术专栏

leetcode-53-Maximum Subarray(动态规划详解)

2164
来自专栏LinkedBear的个人空间

【挑战剑指offer】系列02:替换空格 原

本系列的算法原题来自于“牛客网-剑指offer”,写这个板块,不仅仅是解决算法问题本身,更是手动提高难度、自行变式,思考更多的解决方案,以带给自己一些启发。

1273
来自专栏F_Alex

数据结构与算法(一)-初识

前言:一个程序员前期可能需要各种业务和编程的能力,但是后期如果想要提高就需要有一个扎实的基础,厚积薄发,所以最近抽空学了下数据结构与算法,颇有感触,学习过程虽然...

1192
来自专栏小白的技术客栈

Python之面向对象程序设计-基础知识

面向对象是一种编程范式。范式是指一组方法论。编程范式是一组如何组织代码的方法论。编程范式指的是软件工程中的一种方法学。 主流的编程范式: OOP - 面向对象编...

3605
来自专栏趣学算法

数据结构学习秘籍

网络上太多的同学吐槽被虐,如滔滔江水连绵不绝,数据结构太难了!真的很难吗?其实数据结构只是讲了三种:线性结构、树、图。到底难在哪里呢?通过调查了解大概有四个原因...

1202
来自专栏take time, save time

你所能用到的数据结构(二)

      周末开始更新了,首先感谢各位对我写的东西还能保持兴趣,先回答几个留言中的一个问题和我对无损编码那一节的一个留言的一个看法,第一个是推荐算法书,首先,...

3176
来自专栏take time, save time

Think in 递归

     网上写递归的文章可以用汗牛充栋来形容了,大多数都非常清晰而又细致的角度上讲解了递归的概念,原理等等。以前学生的时候,递归可以说一直是我的某种死穴,原理...

41612
来自专栏Java成长之路

【c语言】简单学生信息管理系统

1.有10个学生,每个学生的数据包括学好、姓名、4门课的成绩、总成绩和平均成绩。从键盘输入10个学生的数据(包括学好、姓名以...

1.1K1
来自专栏数据结构与算法

一种递推组合数前缀和的Trick

\(S(n, m)\)可以看做是杨辉三角上的一行,而\(S(n+1, m)\)是他的下一行

2263
来自专栏ACM算法日常

POJ2318 TOYS 判断点与直线位置关系 【计算几何】

Calculate the number of toys that land in each bin of a partitioned toy box.

1133

扫码关注云+社区

领取腾讯云代金券