《算法分析与设计》2021复习题.pdf
需积分: 24 79 浏览量
2021-05-01
17:31:59
上传
评论 1
收藏 266KB PDF 举报
1 / 6
算法引论
1.衡量一个算法好坏的标准是(算法复杂度低)
2.算法的复杂度有（时间）复杂度和（空间）复杂度之分；
3.（程序）是算法用某种程序设计语言的具体实现；
4.算法是由若干条指令组成的有穷序列，且要满足（输入）（输出）（确定性）（有限性）四
条性质；
5.衡量时间复杂性时，可以考虑（最坏）情况下的时间复杂性、（最好）情况下的时间复杂
性和（平均）情况下的时间复杂性。
6.渐近意义下的记号：若存在正的常数
C
和自然数
N
，使得当
nN
时，
( ) ( )f n Cg n
，则称
()gn
为
()fn
的上界，记为
( ) ( )f n O g n
；
( ) ( )f n Cg n
，则称
()gn
为
()fn
的下界，记为
( ) ( )f n g n
；
当
( ) ( )f n O g n
且
( ) ( )f n g n
时，则称
()gn
与
()fn
同阶，记为
( ) ( )f n g n
；
如果对任意给定的
0
，都存在正整数
N
，使得当
nN
时有
()
()
fn
gn
，则称
()fn
比
()gn
低阶，记为
( ) ( )f n o g n
.
7. 将七个复杂度
nnnnnn
n
log,,2,,3,log,4
3
2
2
按 由 低 到 高 的 顺 序 排 列 :
n
nnnnnn 3,4,log,,,log,2
2
3
2
8.算法的时间复杂性与什么因素相关？
问题的规模、算法的输入、算法本身
9.算法分析的目的：分析算法占用计算机资源的情况，对算法做出比较和评价，设计出更好
的算法
分治法
1.二分搜索算法是以(A)实现的算法
A 分治策略 B 动态规划法 C 贪心算法 D 回溯法
2.Strassen 矩阵乘法是利用（A）实现的算法
A 分治策略 B 动态规划法 C 贪心算法 D 回溯法
3.实现合并排序利用的算法是（A）
A 分治策略 B 动态规划法 C 贪心算法 D 回溯法
4.从分治法的一般设计模式看，用它设计出的程序一般是（递归算法）；
5.大整数乘法是用（分治法）来设计的；
6.快速排序是基于（分治策略）的一种排序算法；
7.分治法的基本思想：将一个规模为 n 的问题分解为 k 个规模较小的子问题，这些子问题互
相独立且与原问题是同类型问题。递归地解这些子问题，然后把各个子问题的解合并得到原
问题的解。
评论0
最新资源