分治算法图文详解

作者: wwwwww31121787
来源: 51数据库
2022-09-22

实际开发中，我们经常会使用一些巧妙的算法解决问题，分治算法就是其中之一。

分治算法是指采用分而治之的思想，将一个复杂的问题划分成很多相互独立的小问题，通过逐个解决这些小问题，使整个问题得到解决。

下图给您描述了分治算法的整个解题过程。

图 1 分治算法

使用分治算法解决问题，大致经历 3 个阶段：

分：将整个问题划分为很多相互独立的小问题（子问题），很多小问题还可以进行更细致地划分，直至这些问题不可再分；
治：逐个解决每个子问题，整个过程通常采用递归的方式实现；
合并：合并所有子问题的解决方案，得到整个问题的解决方案。

分治算法的利弊

分治算法擅长解决一些规模较大的问题，直接解决此类问题的难度较大，通过将大问题“分而治之”，可以简化问题的难度。此外，由于分解得到的诸多小问题之间是相互独立的，所以可以采用并发执行的方式，提高问题的解决效率。

分治算法的缺陷也很明显，该算法常常采用递归的方式实现，整个过程需要消耗大量的系统资源，严重时还会导致程序崩溃。