算法考试小抄必备经典缩印精华-电大-成人自考-大学本科专科.doc
版权申诉
123 浏览量
2022-05-06
13:32:59
上传
评论
收藏 79KB DOC 举报
1、算法的性质：
输入：有外部提供的量作为算法的输
入。
输出：算法产生至少一个量作为输出。
确定性：组成算法的每条指令是清晰、
无歧义的。
有限性（有穷性）：算法中每条指令
的执行次数是有限的，执行每条指令
的时间也是有限的。
2、算法复杂度:算法执行所需的时间和
空间的数量算法的复杂性与求解的问
题规模、算法输入和算法本身有关。
3 、 算 法 的 质 量 指 标 ：（ ） 正 确 性
（）可读性（）稳健性（）高效性
和低存储量要求。
4、在实际的时间复杂度中是否唯一？
不唯一，可能有最好、最坏、平均情
况的时间复杂度。
5、复杂性的渐进性态
设 （）为算法 的时间复杂性函数，
则它是 的单增函数如果存在一个函
数
)(
~
NT
使得当
N
时，有
0
)(
)()(
~
NT
NTNT
称
)(
~
NT
是 当时的渐进性态或渐进
复杂性
6、大 O 表示法 (算法运行时间的上限)
若 存 在 正 常 数 和 自 然 数
0
N
使 得 当
0
NN
时，有
)()( NCgNf
则称函数
在 充分大时有上界且 是它的一
个上界记为
))(()( NgONf
，也称
的阶不高于 的阶。
大 符号用来描述增长率的上限，表
示 的增长最多像 增长的那样快，
也就是说，当输入规模为 时，算法
消耗时间的最大值，这个上限的阶越
低，结果就越有价值。
7、大 W 表示 法 ( 算法运行时间 的下
限）
如果存在正常数 和自然数
0
N
使得当
0
NN
时 ， 有
)()( NCgNf
， 则 称 函 数
在 充分大时有下限，且 是它
的一个下限，记为
))(()( NgNf W
，称
的阶不低于 的阶。
大 W 符号用来描述增长率的下限，也
就是说，当输入规模为 时，算法消
耗时间的最小值。与大 符号对称，
这个下限的阶越高，结果就越有价值。
8、q 表示法
))(()( NgONf
当 且 仅 当
))(()( NgONf
且
))(()( NgNf W
称函数 和 同阶。
q 符号意味着 和 同阶，用来表
示算法的精确阶。
9、算法的渐进复杂性的阶对于算法的
效率有着决定性的意义:
最优算法：时间复杂性达到其下界的
算法。 多项式阶算法有效算法时间
复杂性与规模 的幂同阶。 指数阶算
法时间复杂性与规模 的一个指数函
数同阶。
算法效率 对规模较小的问题决定算
法工作效率的可能是算法的简单性而
不是算法执行的时间
当比较两个算法的效率时若两个算
法是同阶的必须进一步考察阶的常数
因子才能辨别优劣
10、时间复杂性渐进阶分析的规则:(最
坏情况)
赋值、比较、算术运算、逻辑运算、
读写单个变量常量只需 单位时间；
执行条件语句的时
间为 ；选择语
句 ； ；；
需 要 的 时 间 为 （
；访问数组的单
个分量或纪录的单个域需要一个单
位时间。 执行 ! 循环语句的时
间"执行循环体时间# 循环次数；
$%&!'() 语句
时间"#循环次数；*用
从循环体内跳到循环体末或循环后
面的语句时不需额外时间。
第 2 章 分治法
1、分治法的基本思想：将规模为
的问题分解为 + 个规模较小的子
问题使这些子问题相互独立且与
原问题相同，递归地解这些子问题，
然后各个子问题的解合并得到原问
题的解。
2、分治法所能解决的问题一般具
有以下特征：
该问题可以分解为若干个规模较
小的相同问题； 该问题所分解出
的各个子问题是相互独立的，即子
问题之间不包含公共的子问题；
该问题的规模缩小到一定的程度就
可以容易地解决； 利用该问题分
解出的子问题的解可以合并为该问
题的解。
3、分治法的求解过程
分解：把原问题分解为若干个规
模较小、相互独立，与原问题相同
的子问题；求解：若子问题规
模较小且容易被解决则直接解否则
再继续分解为更小的子问题，直到
容易解决；合并：将已求解的各
个子问题的解，逐步合并为原问题
的解。
4、整数划分问题：将正整数 表
示成一系列正整数之和："
…+ ， 其 中 ≥≥…
≥+≥，+≥。正整数 的这种表
示称为正整数 的划分。
5、递归函数的优缺点：优点：算
法简明；正确性易证明，是分析、
设计的有力工具。缺点：执行效率
不高；堆栈空间耗费。
6、线性时间选择：元素选择问题
的一般提法是：给定线性序集中
个元素和一个整数 ，
要求找出这 个元素中第 + 小的元
素。特殊地，当 +" 时，就是要找
最小元素；当 +" 时，就是要找最
大元素；
第 3 章动态规划
1、适用动态规划的问题必须满足
最优化原理 无后效性
2、最优化原理： 一个最优化策
略的子策略总是最优的。 一个问
题满足最优化原理又称其具有最优
子结构性质。最优化原理是动态规
划的基础。任何问题，如果失去了
最优化原理的支持，就不可能
用动态规划方法计算。
3、动态规划的实质：是分治思想
和解决冗余 一种将问题实例分
解为更小的、相似的子问题。存
储子问题的解而避免计算重复的子
问题。
4、动态规划的特点： 动态规划
法用于最优化问题，这类问题会有
多种可能的解，而动态规划找出其
中最优值的解。若存在若干个取最
优值的解的话，它只取其中的一个。
对于重复出现的子问题，只在第
一次遇到时加以求解，并把答案保
存起来，以后再遇到时不必重新求
解。
5、动态规划算法设计步骤
⑴ 分析最优解的性质，并刻划其
结构特征；⑵递归地定义最优值；
⑶以自底向上的方式计算出最优值；
⑷根据计算最优值时得到的信息，
构造最优解。
6、动态规划算法的基本要素 最
优子结构性质 子问题重叠性质
7、最优子结构： 当问题的最优
解包含了其子问题的最优解时，称
该问题具有最优子结构性质。 假
设由最优解导出的其子问题的解不
是最优的；构造出比原问题最优解
更好的解；
8、重叠子问题：每一个子问题只
解一次，而后将其解保存在一个表
格中，当再次需要解此子问题时，
只是简单地用常数时间查看一下结
果。
9、最优化问题：是指对于某类问
题，给定某些约束条件，满足这些
约束条件的问题解称为可行解。为
衡量可行解的好坏，还给出了称为
目标函数的某些数值函数，使目标
函数取的最大（或最小）值的可行
解称为最优解。
10、备忘录方法有哪些特点： 备
忘录方法是动态规划算法的变形。
与动态规划算法一样，备忘录方法
用表格保存已解决的子问题的答案，
在下次需要解此问题时，只要简单
地查看该子问题的解答，而不必重
新计算。与动态规划算法不同的是，
备忘录方法的递归方式是自顶向下
的，而动态规划算法则是自底向上
递归的。因此，备忘录方法的控制
结构与直接递归方法的控制结构相
同，区别在于备忘录方法为每个解
过的子问题建立了备忘录以备需要
时查看，避免了相同子问题的重复
求解。 与动态规划算法一样，备
忘录方法耗时 。
第 4 章 贪心算法
1、动态规划、分治法、贪心法比
较有什么特点？
动态规划法、分治法和贪心法类似，
它们都是将问题实例归纳为更小的、
相似的子问题，并通过求解子问题
产生一个全局最优解。动态规划的
实质是分治思想和解决冗余，因此，
动态规划是一种将问题实例分解为
更小的、相似的子问题，并存储子
问题的解而避免计算重复的子问题，
以解决最优化问题的算法策略；贪
心法的当前选择可能要依赖已经作
出的所有选择，但不依赖于有待于
做出的选择和子问题因此贪心法
自顶向下，一步一步地作出贪心选
择；而分治法中的各个子问题是独
立的即不包含公共的子子问题，
因此一旦递归地求出各子问题的解
后，便可自下而上地将子问题的解合
并成问题的解。但不足的是，如果当
前选择可能要依赖子问题的解时，则
难以通过局部的贪心策略达到全局最
优解；如果各子问题是不独立的，则
分治法要做许多不必要的工作，重复
地解公共的子问题。
2、贪心算法的基本要素：贪心算法通
过一系列的选择来得到问题的解。它
所做的每一个选择都是当前状态下局
部的最好选择，即贪心选择。
基本要素是最优子结构性质贪心
选择性质：是指所求问题的整体最优
解可以通过一系列局部最优的选择，
即贪心选择来达到
3、贪心算法总是做出在当前看来最好
的选择。也就是说贪心算法并不从整
体最优上加以考虑，它所作出的选择
只是在某种意义上的局部最优选择，
即使贪心算法不能得到整体最优解，
但是最终结果也是最优解的很好的近
似值。
4、如何证明一个问题具有贪心选择性
质：
假设问题有一个整体最优解，并证明
可修改这个最优解，使其以贪心选择
开始。运用数学归纳法证明：每一步
贪心选择→问题的整体最优解。
第 5 章回溯法：
1 影响回溯法效率的因素有哪些：产
生 ,+-的时间；满足显约束的 ,+-值
的个数；计算约束函数 ! 的
时间；计算上界函数 .(& 的时间；
满足约束函数和上界函数约束的所
有 ,+-的个数。
2 回溯法-步骤： 针对所给问题，定义
问题的解空间； 确定易于搜索的解空
间结构； 以深度优先方式搜索解空间，
并在搜索过程中用剪枝函数避免无效
搜索。
3、比较回溯算法，分枝限界算法，穷
举法：
回溯法比穷举法效率高：使用约束函
数和限界函数分别剪去不满足约束的
子树和不能产生最优解的子树，避免
无效搜索。所以比穷举法效率高。
回溯法的求解目标是找出解空间中满
足约束条件的所有解，而分支限界法
的求解目标是找到满足约束条件的下
一个解，或是在满足约束条件的解中
找出使某一目标函数值达到极大或极
小的解，即在某种意义下的最优解回
溯法的深度优先方式搜索解空间，而
分支限界法则以广度优先或以最小耗
时优先的方式搜索解空间 分支限界法
与回溯法的主要区别在于对活结点的
扩充方式。
4、回溯法和分枝限界法的解空间树有
子集树和排列树。子集树：当所给的
问题是从 个元素的集合 中找出 满
足性质的子集时，相应的解空 间 树
称为子集树。排序树：当所给问题是
确定 个元素满足某种性质的排列时，
相应的解空间树称为排列树。
5、活结点：深度优先；死结点：不能
向纵深方向移动。
6、剪枝函数：用约束函数在扩展结点
处剪去不满足约束的子树；用限界函
数剪去得不到最 优解的子树。
7、满足所有约束条件的解状态结点称
为回答结点。
资源评论
