算法与数据结构 ：带你了解分治算法之美

前言
这次分享的内容是，经典算法思想-分治，你可以把它称之为一种思想，也可以叫它分治算法，为了更好的区分，接下来我们以'分治法'来称呼它。

如果你还不了解什么是分治法，或者知道一些，但是对于它具体是如何实现回溯，那么这篇文章可能适合你阅读。

我对分治算法的理解：

• 它的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。
• 求出子问题的解，就可得到原问题的解，可以理解成一种分目标完成程序的算法。
• 二分法很多时候，就是一种分治的思想。

那么围绕以下几个点来展开介绍分治算法👇

• 基本思路
• 适用情况以及求解哪些经典问题
• 经典例题

分治法基本思想
一句话，对分治法概括它的话👇

将原问题划分成n个规模较小而结构与原问题相似的子问题，递归去解决这些子问题，然后依次再合并其结果，最后得到原问题的解。

那么具体的来说，我们似乎可以分成三个步骤👇

• 分解：将要解决的问题划分成若干规模较小的同类问题。
• 解决：当子问题划分得足够小时，用较简单的方法解决。
• 合并：按原问题的要求，将子问题的解逐层合并构成原问题的解。

其实思想还是不变的，将一个难以直接解决的大问题，分割成一些小规模的相同问题，以便各个击破，分而治之。

分治法适用情况
利用分治法求解一个问题，在于我们能否掌握分治法的几个特征：

1. 鸿蒙官方战略合作共建——HarmonyOS技术社区
2. 把一个问题可以缩小到一定程度，变成更小的问题来解决。
3. 分解成若干个小问题后，规模更小且是同类问题，这样子的话，该问题应该就是最优子结构。
4. 利用该问题分解出来的子问题的解，合并为该问题的解。
5. 分解出来的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

那我们来说一说这几个特征吧~

第一条特征：一个问题的计算复杂性一般是随问题的规模增加而增加的，所以绝大多数问题都满足。

第二条特征：应用分治法的前提是得满足它，你可以理解成它某种程度上反映了递归思想的应用。

第三条特征：这个应该就是分治法的关键了吧，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。

（编辑：伊春站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!