首页 ›存档› 技术 › 查看内容

PHP算法学习之分治法

2018-3-30 13:00 |来自: 互联网 323 0

摘要: 分治法，顾名思义就是分而治之，即把问题拆解为性质相同的小问题再处理。做了一些题后发现，分治法除了分治，名字里还少了一步，那就是合，也就是怎样通过小问题的答案得到拆分之前大问题的答案。分治法的时间复杂 ...

分治法，顾名思义就是分而治之，即把问题拆解为性质相同的小问题再处理。

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

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

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

1、前序遍历二叉树

2、求二叉树的最大路径和
给一棵二叉树，找出从根节点出发的路径中，和最大的一条。
这条路径可以在任何二叉树中的节点结束，但是必须包含至少一个点。

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

4、快速排序
这里我就偷个懒，直接贴出百度百科上给的php标准答案~

--------------伟大的分割线----------------

PHP饭米粒(phpfamily) 由一群靠谱的人建立，愿为PHPer带来一些值得细细品味的精神食粮！

饭米粒只发原创或授权发表的文章，不转载网上的文章

所发的文章，均可找到原作者进行沟通。

也希望各位多多打赏（算作稿费给文章作者），更希望大家多多投搞。

投稿请联系：

[email protected]

本文由 ShutLove 向饭米粒投稿，转载请注明本来源信息和以下的二维码（长按可识别二维码关注）