devbox
盐析白兔
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法之分治算法

作者：盐析白兔 | 2024-06-14 04:40:56

赞

踩

分治算法

1.分治算法

「分治 divide and conquer」，全称分而治之，是一种非常重要且常见的算法策略。分治通常基于递归实现，包括“分”和“治”两个步骤。
1. 分（划分阶段） ：递归地将原问题分解为两个或多个子问题，直至到达最小子问题时终止。
2. 治（合并阶段） ：从已知解的最小子问题开始，从底至顶地将子问题的解进行合并，从而构建出原问题的解。
如下图所示，“归并排序”是分治策略的典型应用之一。
1. 分 ：递归地将原数组（原问题）划分为两个子数组（子问题），直到子数组只剩一个元素（最小子问题）。
2. 治 ：从底至顶地将有序的子数组（子问题的解）进行合并，从而得到有序的原数组（原问题的解）。

 1.1如何判断分治问题

一个问题是否适合使用分治解决，通常可以参考以下几个判断依据。
1. 问题可以被分解 ：原问题可以被分解成规模更小、类似的子问题，以及能够以相同方式递归地进行划分。
2. 子问题是独立的 ：子问题之间是没有重叠的，互相没有依赖，可以被独立解决。
3. 子问题的解可以被合并 ：原问题的解通过合并子问题的解得来。
显然，归并排序是满足以上三条判断依据的。
1. 问题可以被分解 ：递归地将数组（原问题）划分为两个子数组（子问题）。
2. 子问题是独立的 ：每个子数组都可以独立地进行排序（子问题可以独立进行求解）。
3. 子问题的解可以被合并 ：两个有序子数组（子问题的解）可以被合并为一个有序数组（原问题的解）。

1.2 通过分治提升效率

分治不仅可以有效地解决算法问题， 往往还可以带来算法效率的提升 。在排序算法中，快速排序、归并排序、堆排序相较于选择、冒泡、插入排序更快，就是因为它们应用了分治策略。
那么，我们不禁发问： 为什么分治可以提升算法效率，其底层逻辑是什么 ？换句话说，将大问题分解为多个子问题、解决子问题、将子问题的解合并为原问题的解，这几步的效率为什么比直接解决原问题的效率更高？ 这个问题可以从操作数量和并行计算两方面来讨论。
1. 操作数量优化
以“冒泡排序”为例，其处理一个长度为 声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。