php语言 百文网手机站

PHP算法学习之分治法

时间:2021-04-09 09:16:22 php语言 我要投稿

PHP算法学习之分治法

  分治法,顾名思义就是分而治之,即把问题拆解为性质相同的小问题再处理。下面小编为大家整理了PHP算法学习之分治法,希望能帮到大家!

PHP算法学习之分治法

  做了一些题后发现,分治法除了分治,名字里还少了一步,那就是合,也就是怎样通过小问题的答案得到拆分之前大问题的答案。

  分治法的时间复杂度:分治法并没有像二分法一样每次丢掉一半无用的'解,它只是做了分离,而分离的两部分都是需要处理的,所以分治法的时间复杂度是O(n)。特例情况是当分离的两部分继续分治处理出现重复计算的情况时,就会比O(n)大了!所以请确保你的分治尽量不要出现重叠计算的情况。

  那么什么问题适合用分治的思想解决呢?二叉树!二叉树这种左右子树的结构天生就非常适合分治,所以它的大部分问题都能用分治解决,碰到一个问题你只需要问问左子树你怎么处理,右子树你怎么办,得到左右子树的答案后,你再想想最后的答案是个啥~除了二叉树,快速排序归并排序这两个著名的排序算法也是分治的思想。下面就举几个解题的例子来加深一下对分治法的学习。

  1、前序遍历二叉树

  2、求二叉树的最大路径和

  给一棵二叉树,找出从根节点出发的路径中,和最大的一条。

  这条路径可以在任何二叉树中的节点结束,但是必须包含至少一个点。

  3、求最近公共祖先

  给定一棵二叉树,找到两个节点的最近公共父节点(LCA),给出的两个节点都在树中存在。

  4、快速排序

  这里我就偷个懒,直接贴出百度百科上给的php标准答案~

【PHP算法学习之分治法】相关文章:

php算法学习之动态规划09-27

php算法学习之宽度优先搜索09-28

php学习之php配置09-09

PHP红包算法09-26

php学习之php预定义变量09-16

PHP经典算法题09-25

php经典算法介绍09-04

PHP排序算法类讲解09-30

PHP可逆加密解密算法09-26