算法设计与分析——（各种解决问题的方法）之分治算法、动态规划算法
算法设计与分析——（各种解决问题的方法）之分治算法、动态规划算法
★上一期详细介绍了迭代算法和蛮力算法,感兴趣的同学可以点击链接查看文章哦！！！
https://blog.csdn.net/2302_76516899/article/details/138822082
目录
一、分治算法
这里是两篇通过分治算法解决的问题可供大家参考喔！！
https://blog.csdn.net/2302_76516899/article/details/138791015
https://blog.csdn.net/2302_76516899/article/details/138732662
🍓什么是分治算法
分治算法是一种解决问题的方法，它将一个复杂的问题分解成两个或多个相似的子问题，直到这些子问题简单到可以直接求解。然后，这些子问题的解决方案被合并以产生原始问题的解决方案。
🍉基本思想
分治策略的核心在于将一个难以直接解决的大问题，分割成一些规模较小的同类问题，以便于容易计算，然后递归解决这些子问题，最后再将所有子问题的解合并起来解决原来的大问题。
🍉步骤
- 分解（Divide）：将原问题分解成一系列子问题。这些子问题相互独立，且与原问题形式相同只是规模更小。
- 解决（Conquer）：递归地解决这些子问题。如果子问题的规模足够小，则直接解决。
- 合并（Combine）：将子问题的解合并为原问题的解。
🍓示例
假设我们要解决一个经典的问题：在一个数组中查找最大值。我们可以使用分治算法来解决这个问题。
1.分解（Divide）
首先，将数组分成较小的子数组，直到每个子数组都很容易解决。这可以通过递归地将数组划分成更小的部分来完成。
2.解决（Conquer）
对每个子数组应用相同的算法，直到基本情况下的问题得到解决。对于这个问题，基本情况就是一个包含一个元素的数组，因为在一个元素的数组中，最大值就是这个元素本身。
3.合并（Combine）
将子问题的解合并成原始问题的解。对于最大值的问题，只需比较所有子数组的最大值，并返回其中最大的那个。
🍓演示过程
★分解过程
[3, 6, 8, 2, 10, 5, 7, 4]
/ \
[3, 6, 8, 2] [10, 5, 7, 4]
/ \ / \
[3, 6] [8, 2] [10, 5] [7, 4]
/ \ / \ / \ / \
[3] [6] [8] [2] [10] [5] [7] [4]
在这个示意图中，我们从根节点开始，将数组一分为二，然后继续分割，直到到达基本情况，即包含一个元素的数组。然后，我们开始合并过程，比较每个子数组的最大值，直到得到整个数组的最大值。
★合并过程
[3, 6, 8, 2, 10, 5, 7, 4]
/ \
[3, 6, 8, 2] [10, 5, 7, 4]
/ \ / \
[6] [8] [10] [7]
\ / \ /
[8] [10] [10] [7]
\ / \ /
[10] [10]
\ /
[10] [10]
\ /
[10, 10]
\
[10, 10, 10]
在这个示意图中，我们从底部开始，将每个子数组的最大值两两比较，选择其中较大的值。然后将这些较大值再次两两比较，直到最后得到整个数组的最大值。
🍓分治算法的效率
🍌分析
分治算法的时间复杂度和空间复杂度通常取决于以下几个因素：
★ 子问题的数量
分治算法将问题分解成若干个子问题，如果子问题的数量较大，那么算法的时间复杂度通常会更高。
★ 子问题的规模
每个子问题的规模是指其输入数据的大小，如果子问题的规模较小，那么解决每个子问题的时间会更短。
★合并操作的复杂度
在分治算法中，将子问题的解合并起来通常需要一定的时间，合并操作的复杂度会影响总体的时间复杂度。
🍌时间复杂度
★分治算法的时间复杂度取决于三个因素：分解步骤的复杂度、合并步骤的复杂度以及递归深度。通常情况下，分解和合并步骤的复杂度是相同的，并且递归深度取决于问题的规模以及分解的方式。如果每次分解能将问题的规模减少为原来的一半，那么递归深度将是 O(log n) 级别的。
★如果用T(n)表示问题规模为n时分治算法的时间复杂度，那么可以通过递归关系或者递归树来推导T(n)。如果子问题的数量为a，每个子问题的规模为b，合并操作的时间复杂度为O(f(n))，那么分治算法的时间复杂度可以表示为：
★T(n) = a * T(n/b) + O(f(n))
★其中，a、b、f(n)是常数。根据主定理或者递归树的性质，可以推导出T(n)的表达式，从而确定时间复杂度的级别。
🍌空间复杂度
★分治算法的空间复杂度主要取决于递归调用所需要的栈空间以及其他临时变量的空间占用。如果算法涉及到递归调用，那么每次调用都会在栈上分配一定的空间，因此空间复杂度通常与递归的深度有关。除此之外，合并操作可能需要额外的空间来存储临时数据。
🍓分治算法的优缺点
🍍优点：
★高效性
分治算法通常能够将问题分解成规模较小的子问题，从而减少了问题的复杂度，提高了解决问题的效率。
★模块化
分治算法将问题分解成独立的子问题，使得算法结构清晰，易于理解和实现。
★并行性
分治算法的子问题通常是相互独立的，可以并行地求解，从而提高了算法的并行性和性能。
★适用性广泛
分治算法是一种通用的问题求解思想，适用于很多领域，如排序、搜索、优化等。
🍍缺点：
★空间复杂度高
分治算法通常需要额外的空间来存储中间结果和递归调用的栈空间，因此在一些空间敏感的应用场景下可能不太适用。
★递归调用开销大
分治算法通常通过递归来实现，递归调用会增加额外的开销，可能导致算法的性能下降。
★不适用于所有问题
分治算法并不是对所有问题都适用的，有些问题可能难以分解成独立的子问题，或者合并操作复杂度较高，这时候分治算法可能并不是最佳选择。
🍍总的来说，分治算法在解决一些特定类型的问题时表现出色，但在其他情况下可能并不适用。选择是否使用分治算法需要根据具体的问题特点和需求来决定。
二、动态规划算法
🍓什么是动态规划算法
动态规划算法通常用于解决具有重叠子问题和最优子结构性质的问题。它将问题分解成若干个重叠的子问题，并通过解决这些子问题来求解原始问题。
🍉动态规划算法步骤
🍌划分子问题
★ 将原问题划分成若干个重叠的子问题，这些子问题通常具有最优子结构性质，即原问题的最优解可以通过子问题的最优解来求解。
🍌确定状态
★ 定义问题的状态，即描述问题当前的特征。状态的选择通常与子问题相关联，并且状态之间具有转移关系。
🍌建立状态转移方程
★根据子问题之间的转移关系，建立状态转移方程，用于描述子问题之间的关系，从而推导出问题的解。
🍌初始化
★初始化动态规划表格，将问题的初始状态填入表格中。
🍌填表求解
★根据状态转移方程和初始状态，依次填充动态规划表格，直到填满整个表格。
🍌解析结果
★根据填满的动态规划表格，找到问题的最优解或者所需结果。
🍓示例
★假设我们要求解斐波那契数列的第n个数，可以使用动态规划算法来解决。
下面是一个演示动态规划算法解决斐波那契数列的过程的图示：
0 1 1 2 3 5 8 13 21
n=0 |0| |
n=1 |0| 1 | |
n=2 |0| 1 | 1 | |
n=3 |0| 1 | 1 | 2 | |
n=4 |0| 1 | 1 | 2 | 3 | |
n=5 |0| 1 | 1 | 2 | 3 | 5 | |
表格中的每个元素表示斐波那契数列中对应位置的数值，表格的行表示斐波那契数列的索引n，表格的列表示斐波那契数列中对应位置的数值。我们可以通过填表的方式来求解斐波那契数列的第n个数。
首先，初始化表格，将已知的斐波那契数列中的前两个数填入表格中。
然后，根据斐波那契数列的递推关系，依次填充表格中的其他位置，直到填满整个表格。
最后，根据填满的表格，找到斐波那契数列中第n个数的值。
在这个例子中，动态规划算法通过填表的方式避免了重复计算，提高了求解斐波那契数列的效率。
🍓动态规划算法效率
🍌分析
动态规划算法的时间复杂度和空间复杂度通常取决于以下几个因素：
★子问题的数量
动态规划算法将问题分解成若干个子问题，并通过填表的方式逐步求解子问题，子问题的数量会影响算法的时间复杂度和空间复杂度。
★子问题的规模
每个子问题的规模是指其输入数据的大小，规模较大的子问题通常需要更多的时间和空间来求解。
★状态转移方程的复杂度
状态转移方程描述了子问题之间的转移关系，如果状态转移方程的计算复杂度较高，那么算法的时间复杂度会相应增加。
🍌时间复杂度
★如果用T(n)表示问题规模为n时动态规划算法的时间复杂度，那么可以通过填表的方式来推导T(n)。通常情况下，如果子问题的数量为n，每个子问题的规模为m，那么动态规划算法的时间复杂度可以表示为：
★T(n) = O(n * m)
★其中，n表示问题规模，m表示子问题的规模。动态规划算法通常是自底向上地填表，填表的过程需要遍历整个表格一次，因此时间复杂度与表格的大小成正比。
🍌空间复杂度
★动态规划算法的空间复杂度通常取决于填表过程中所需要的存储空间。如果用S(n)表示问题规模为n时动态规划算法的空间复杂度，那么通常情况下可以表示为：
★S(n) = O(n * m)
★其中，n表示问题规模，m表示子问题的规模。动态规划算法通常需要一个二维的表格来存储中间结果，表格的大小与问题规模和子问题规模相关，因此空间复杂度与表格的大小成正比。
🍌总的来说，动态规划算法的时间复杂度和空间复杂度都与问题规模和子问题规模相关，通常是多项式时间复杂度和多项式空间复杂度。
🍓动态规划算法优缺点
🍍优点
★高效性
动态规划算法通常能够通过填表的方式避免重复计算，从而提高了算法的效率。
★可解决复杂问题
动态规划算法能够解决一些具有重叠子问题和最优子结构性质的复杂问题，如最长递增子序列、0-1背包问题、最短路径问题等。
★优化性能
动态规划算法能够通过存储中间结果来避免重复计算，从而提高了算法的性能。
★模块化设计
动态规划算法通常采用填表的方式求解问题，使得算法结构清晰，易于理解和实现。
🍍缺点
★空间复杂度高
动态规划算法通常需要一个二维的表格来存储中间结果，表格的大小与问题规模和子问题规模相关，因此空间复杂度较高。
★状态转移方程复杂
在一些问题中，状态转移方程可能比较复杂，难以推导出有效的动态规划算法。
★不适用于所有问题
动态规划算法并不是对所有问题都适用的，只有具有重叠子问题和最优子结构性质的问题才适合采用动态规划算法。
🍍总的来说，动态规划算法是一种非常重要且常用的算法思想，能够解决许多复杂的优化问题。但在使用动态规划算法时，需要权衡算法的效率和空间占用，并根据具体的问题特点和需求来选择合适的算法。
三、分治算法与动态规划法异同点
🍓相同点
问题分解： 两种算法都将原始问题分解成若干个子问题，并通过解决这些子问题来求解原始问题。
递归思想： 分治算法和动态规划算法都使用了递归的思想，通过递归地解决子问题来求解原始问题。
🍓不同点
🍍重复子问题处理方式：
1.分治算法： 在分治算法中，每个子问题只会被解决一次，不会出现重复计算的情况。
2.动态规划算法： 动态规划算法通过存储中间结果来避免重复计算，即将已经解决过的子 问题的解存储起来，在需要时直接利用，而不需要重新计算。
🍍最优子结构性质：
1.分治算法： 分治算法通常要求原始问题具有最优子结构性质，即原始问题的最优解可以通过子问题的最优解来求解。
2.动态规划算法： 动态规划算法也要求原始问题具有最优子结构性质，但同时还需要子问题之间存在重叠子问题，即子问题之间存在公共的子问题。
🍍解题方式：
1.分治算法： 分治算法通常通过将原问题分解成独立的子问题来求解，子问题之间不存在依赖关系，各自独立求解。
2.动态规划算法： 动态规划算法通过填表的方式来求解问题，需要事先确定问题的状态和状态转移方程，并利用中间结果来避免重复计算。
🍍总的来说，分治算法和动态规划算法在解决问题时有着不同的思路和处理方式，选择使用哪种算法取决于问题的性质和特点。
希望这些能对刚学习算法的同学们提供些帮助哦！！！
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
24
0- 0
已为社区贡献16条内容
所有评论(0)