算法设计与分析复习资料
一、基本概念与知识点,考查形式主要为选择题和填空题(50 分左右)
(1)算法定义与特征
例:算法是由若干条指令组成的有穷序列,需要满足输入、输出、确定性、有效性和有限
性。
(2)算法效率度量方法
例:假设算法 A 理论上的时间复杂度 T(n)=O(n
2
),现在有两台同类型计算机 M1 和 M2,
M2 的计算速度是 M1 的 x 倍。若在 M1 和 M2 上分别测试算法 A,则在相同时间内,M1
和 M2 能够求解的问题规模 n1 和 n2 的关系。求解相同规模,两台机器耗费时间关系。
(3)对于分治法求解问题的算法复杂性理论分析
�
�
�
��
�
�
1)()/(
1)1(
)(
nnfbnaT
nO
nT
,对于给定 a,b 和 f(n)的不同情况,判断算法时间复杂
度。
例:对于某一具体问题,若 f(n) = O(1)且 a=2
,
b=2,则求解该问题的时间复杂度为 O(n)
(4)课堂所讲授的分治、动态规划、贪心、回溯、分支限界、遗传等算法基本思想,求解
问题步骤,关键点,时间/空间复杂度分析结论。不同算法适合求解的经典问题。
例:在无序序列中查找最大值,若采用分治法查找,则求解该问题的算法时间复杂度为
()
适合采用动态规划算法求解的代表性问题是()
回溯法求解旅行售货员问题时的解空间树是什么树
适合采用动态规划算法或贪心算法求解的问题具备的共同特征是
求解以下问题的动态规划算法中,空间复杂度最小的是
评论0