文档介绍：算法的概念
算法的特征
算法的描述
算法设计中常用的基本方法
算法的设计要求
算法的评价
算法的概念
算法就是为解决一个特定问题而采取的方法和步骤。
举法
算法设计中常用的基本方法
递归是设计和描述算法的一种有力的工具，在用计算机解决某些复杂的问题时，使用递归是十分有效的。递归过程一般通过函数或子过程来实现，在函数或子过程的内部，直接或者间接地又调用到了自身，这种用递归来描述的算法称之为递归算法。
递归法
算法设计中常用的基本方法
能采用递归描述的算法的特点：
将求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。
特别地，当规模N=1时，能直接得解。递归算法的执行过程分递推和回归两个阶段。在递推阶段，把较复杂的问题（规模为N）的求解推到比原问题简单一些的问题（规模小于N）的求解。
递归法
算法设计中常用的基本方法
在使用递归的算法中，必须包含下面两个关键点：
1
2
必须有一个明确的递归终止条件，即递归出口
函数或过程的调用中包含它本身
回溯法
算法设计中常用的基本方法
回溯法也称为试探法，该方法放弃关于问题规模大小的限制，并将问题的方案按某种顺序逐一枚举和试验。发现当前方案不可能有解时，就选择下一个方案，倘若当前方案不满足问题的要求时，继续扩大当前方案的规模，并继续试探。如果当前方案满足所有要求时，该方案就是问题的一个解。在回溯中，放弃当前方案，寻找下一个方案的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。
运用回溯法解题的步骤：
（1）针对所给问题，定义问题的解空间
回溯法
算法设计中常用的基本方法
（2）确定易于搜索的解空间结构
（3）以深度优先的方式搜索解空间，并且在搜索
过程中用剪枝函数避免无效搜索
注意：
由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法
分治法
分治法，顾名思义，就是“分而治之”的意思。就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题······直到最后子问题可以简单直接求解，原问题的解即子问题的解的合并。
算法设计中常用的基本方法
分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
分治法的分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分割为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
分治法
算法设计中常用的基本方法
1
2
3
4
该问题的规模缩小到一定的程度就可以容易地解决
该问题可以
分割为若干个规模较
小的相同问题，即该问题具有最优子结构性质
该问题可以分割为若干个规模较小的相同问题，即该问题具有
最优子结构
性质
利用该问
题分割出的子问题
的解可以合并为该问题的解
分治法所能解决的问题一般具有以下几个特征：
分治法
算法设计中常用的基本方法
分治法在每一层递归上都有3个步骤：
分割：
将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。
求解：
若子问题规模较小而且容易解决则直接解决，否则递归地解各个子问题。
合并：
将各个子问题的解合并为原问题的解。
2
3
1
分治法
算法设计中常用的基本方法
二分查找法就是分治法的一种简单形式，适用于在有序的线性表中查找某个数据元素的位置。
利用分治策略求解时，所需时间取决于分解后子问题的个数、子问题的规模大小等因素。二分查找法划分简单、均匀，是经常采用的一种有效方法。
算法的设计要求