算法设计与分析要点复习：
一、基本概念
1、什么是算法？算法是求解一类问题的人以一种特殊的方法。

一个算法是对特
定问题求解步骤的一种描述，它是指令的有限序列。

2、算法有那些特性？输入、输出、确定性、能行性、有穷性。

3、评估一个算法的指标有那些（或者说分析一个算法的优劣主要考虑的因素）？
正确性、简明性、效率、最优性。

4、算法运行的时间代价的度量不应依赖于算法运行的软件平台，算法运行的软
件包括操作系统和采用的编程语言及其编译系统。

时间代价用执行基本操作（即关键操作）的次数来度量，这是进行算法分析的基础。

5、基本操作（即关键操作）是指算法运行中起主要作用且花费最多时间的操作。

6、基本操作是个概念，无法具体定义。

问题的实例长度是指作为该问题的一个
实例的输入规模的大小。

这个概念也很难精确定义。

算法的时间（或）空间复杂度是由问题实例长度的函数来表示的。

即：一个算法的时间代价由该算法用于问题长度为n的实例所需要的基本操作次数来表示。

7、算法的时间复杂度、空间复杂度。

T(n)、S(n)
8、在实际的算法中T(n)是否唯一？不唯一。

可能有最好、最坏、平均情形的时
间复杂度。

9、算法与程序的区别？
10、算法按计算时间可分为两类：多项式是时间算法、指数时间算法。

最常
见的多项式时间算法的渐进时间复杂度之间的关系为：O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)
最常见的指数时间算法的渐进时间复杂度之间的关系为：O(2n)<O(n!)< O(n n)
11、算法的作用和地位？
12、算法问题的求解过程是怎样的？如下图所示：
13、
14、简述分治法是怎样的一种算法设计策略。

15、二分查找算法的实现前提？
16、为什么要对二叉排序树进行平衡操作？
17、什么是平衡因子？什么是二叉平衡树？二叉平衡树对平衡因子的取值有
什么要求？
18、最优化问题：是指对于某类问题，给定某些约束条件，满足这些约束条
件的问题解称为可行解。

为衡量可行解的好坏，还给出了称为目标函数的某个数值函数，使目标函数取的最大（或最小）值的可行解称为最优解。

19、贪心算法总是做出在当前看来是最好的选择。

也就是说贪心算法并不从
整体最优上加以考虑，它所作出的选择只是在某种意义上的局部最优选择，即使贪心算法不能得到整体最优解，但其最终结果也是最优解的很好的近似解。

20、贪心选择的基本要素：贪心选择性质、最优子结构性质
21、动态规划算法的基本要素：最优子结构性质、子问题重叠性质。

22、动态规划算法与分治法、贪心法比较有何特点？
23、比较回溯算法、分枝限界算法。