动态分治算法

⑴ 递归，分治算法，动态规划和贪心选择的区别

递归，简单的重复，计算量大。 分治，解决问题独立，分开计算，如其名。 动态规划算法通常以自底向上的方式解各子问题， 贪心算法则通常以自顶向下的方式进行； 动态规划能求出问题的最优解，贪心不能保证求出问题的最优解

⑵ 分治算法时间复杂度

一：分治算法和递归
1.简述递归

我们要讲到分治算法，我觉得有必要说一下递归，他们就像一对孪生兄弟，经常同时应用在算法设计中，并由此产生许多高效的算法。
直接或间接的调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。

int fibonacci(int n){
if (n <= 1) return 1;
return fibonacci(n-1)+fibonacci(n-2);
}
先简单看一下经典的递归例子，博主会找个时间系统详细的总结一下关于递归的内容。

2.简述分治

分治法的设计思想是：

分–将问题分解为规模更小的子问题；
治–将这些规模更小的子问题逐个击破；
合–将已解决的子问题合并，最终得出“母”问题的解；
一个先自顶向下，再自底向上的过程。

凡治众如治寡，分数是也。—孙子兵法

3.分治法与递归的联系

由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。

二：分治法的适用条件
分治法所能解决的问题一般具有以下几个特征：

1) 该问题的规模缩小到一定的程度就可以容易地解决
2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
3) 利用该问题分解出的子问题的解可以合并为该问题的解；
4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

第一条特征是绝大多数问题都可以满足的，因为问题的复杂性一般是随着问题规模的增加而增加；

第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；、

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

第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好

三：分治法的基本步骤
分解问题：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；（自顶向下）
这里涉及到一个平衡子问题的思想：人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡子问题的思想，它几乎总是比子问题规模不等的做法要好。

解决问题：如果问题规模较小而容易被解决则直接解，否则递归地解各个子问题，以得到小问题的解。
合并结果：将各个子问题的解合并为原问题的解：（自底向上）。
它的一般算法设计模式如下：
divide-and-conquer(P){
if ( | P | <= n0) adhoc(P); //（2）解决问题：递归到小问题，则解决小规模的问题（自顶向下）
divide P into smaller subinstances P1,P2,...,Pk；//（1）分解问题
for (i=1,i<=k,i++)
yi=divide-and-conquer(Pi); //利用递归的解各子问题
return merge(y1,...,yk); //将各子问题的解合并为原问题的解（自底向上）
}
四：分治法的复杂性分析
从分治法的一般设计模式可以看出，用他设计出的程序一般是递归算法。因此分治法的计算效率通常可以用递归方程来进行分析。
一个分治法将规模为n的问题分成k个规模为n/m的子问题去解。设分解阀值（表示当问题P规模不超过n0时，问题已容易解出，不必再继续分解）n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：

通常可以用展开递归式的方法来解这类递归方程，反复带入求解得

⑶ 比较“分治法”和“动态规划法”的异同点和优缺点

共同点：
将待求解的问题分解成若干子问题，先求解子问题，然后再从这些子问题的解得到原问题的解。
不同点：
1、适合于用动态规划法求解的问题，分解得到的各子问题往往不是相互独立的；
而分治法中子问题相互独立。
2、动态规划法用表保存已求解过的子问题的解，再次碰到同样的子问题时不必重新求解，而只需查询答案，故可获得多项式级时间复杂度，效率较高；
而分治法中对于每次出现的子问题均求解，导致同样的子问题被反复求解，故产生指数增长的时间复杂度，效率较低。

⑷ 动态规划算法的基本思想

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。

拓展资料：

动态规划的实质是分治思想和解决冗余，因此动态规划是一种将问题实例分析为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略
动态规划所针对的问题有一个显着的特征，即它对应的子问题树中的子问题呈现大量的重复。动态规划的关键在于，对于重复的子问题，只在第一次遇到时求解，并把答案保存起来，让以后再遇到时直接引用，不必要重新求解。