算法的定义.docx

1算法的定义
算法(Algorithm)是一系列解决问题的清晰指令，也就是说，能够对 一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有 缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不 同的算法可能用不同的时间、空要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当
n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的 问题，有时是相当困难的。
分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规 模较小的相同问题，以便各个击破，分而治之。
分治策略是:对于一个规模为n的问题，若该问题可以容易地解决（比 如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问 题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题， 然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分 治法。
如果原问题可分割成k个子问题，1<kWn，且这些子问题都可解并 可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。 由分治法产生的子问题彳主彳主是原问题的较小模式，这就为使用递归技 术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与 原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直 接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄 弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
分治法所能解决的问题一般具有以下几个特征：
该问题的规模缩小到一定的程度就可以容易地解决；
该问题可以分解为若十个规模较小的相同问题，即该问题具有最 优子结构性质。
利用该问题分解出的子问题的解可以合并为该问题的解；
该问题所分解出的各个子问题是相互独立的，即子问题之间不包
含公共的子问题。
上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复 杂性一般是随着问题规模的增加而增加;第二条特征是应用分治法的 前提它也是大多数问题可以满足的，此特征反映了递归思想的应用； 第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条 特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可 以考虑用贪心法或动态规划法。第四条特征涉及到分治法的效率，如 果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公 共的子问题，此时虽然可用分治法，但一般用动态规划法较好。
分治法的运用关键在于解决三个问题：
确定分治规则，即如何分解问题。
[?1
确定终结条件，即问题分解到什么状态时可以直接求解。
[?1 一 . ， .一、
确定归纳方法，即如何由子问题的解得到原问题的解。这一步并
[2
不总是需要的，因为对某些问题来说，并不需要对子问题的解进行复 杂的归纳。

动态规划法多用来计算最优问题，动态规划法与分治法的基本思想是 一致的，但处理的手法不同。动态规划法在运用时，要先对问题的分 治规律进行分析，找出终结子问题，以及子问题向父问题归纳的规则， 而算法则直接从终结子问题开始求解，逐层向上归纳，直到归纳出原 问题的解。
动态规划法多用于在分治过程中，子问题可能重复出现的情况，在这
种情况下，如果按照常规的分治法，自上向下分治求解，则重复出现 的子问题就会被重复地求解，从而增大了冗余计算量，降低了