计算机算法设计与分析知识点整理.pdfVIP

算法是一系列解决问题的清晰指令，也就是说，能够对符合一定规范的输入，在有限时间内

获得所要求的输出。简单的说，就是解决问题的一种方法或过程。

算法－特征：（1）确定性（2）多样性（3）有穷性（4）输出

所需资源越少，该算法越好，计算机最重要的资源是时间和空间

把基本操作（最重要的操作）次数作为算法运行时间的度量单位。

•T(n)≈cC(n)

op

基本操作的执行时间基本操作次数

算法输入规模n为时间效率的参数

算法的时间效率和空间效率都用输入规模的函数进行度量

O(g(n))是增长次数小于等于g(n)(以及其常数倍，n趋向于无穷大)的函数集合。

符号О

成立条件：对于所有足够大的n，t(n)的上界由g(n)的常数倍数所确定。即，存在大于0

的常数c和非负的整数n，使得：对于所有的n≥n来说，t(n)≤cg(n)

00

Ω(g(n))代表增长次数大于等于g(n)(以及其常数倍,n趋向于无穷大)的函数集合

符号Ω

成立条件：对于所有足够大的n，t(n)的下界由g(n)的常数倍所确定，

即，存在大于0的常数c和非负的整数n，使得：

0

对于所有的n≥n来说，t(n)≥cg(n)

0

Θ(g(n))是增长次数等于g(n)(以及其常数倍,n趋向于无穷大)的函数集合。

符号Θ

成立条件：对于所有足够大的n，t(n)的上界和下界都由g(n)的常数倍数所确定，

即，存在大于0的常数c，c和和非负的整数n，使得：

120

对于所有的n≥n来说，cg(n)≤t(n)≤cg(n)

021

算法的整体效率是由具有较大的增长次数的部分所决定的，即它的效率较差的部分。

1

logn

n

nlogn

2

n

3

n

2n

n!

动态规划算法的基本要素

（1）最优子结构性质（2）重叠子问题性质

矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质

递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这

种性质称为子问题的重叠性质

动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此

子问题时，只是简单地用常数时间查看一下结果

通常不同的子问题个数随问题的大小呈多项式增长

动态规划算法的步骤

(1)找出最优解的性质，并刻划其结构特征。

(2)递归地定义最优值。

(3)以自底向上的方式计算出最优值。

(4)根据计算最优值时得到的信息，构造最优解。

基本思想也是将待求解问题分解成若干个子问题,能够保存已解决的子问题的答案，而在

需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法

贪心法只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这

个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种

意义上的局部最优,这种局部最优选择并不总能获得整体最优解（OptimalSolution），但通常

能获得近似最优解

贪心法求解的问题的特征：

（1）最优子结构性质

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称

此问题满足最优性原理。

（2）贪心选择性质

所谓贪心选择性质是指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择

来得到。

动态规划法通常以自底向上的方式求解各个子问题，而贪心法则通常以自