算法分析与设计基础概念整理

1.算法的特征：输入（零个或多个输入量）、输出（至少产生一个输出量）、确定性（算法每一条指令都有确切的定义，没有二义性）、能行性（算法每一条指令必须足够基本，他们通过已经实现的基本运算执行有限次来实现）、有穷性
2.描述一个算法有多种方法，可以用自然语言、流程图、伪代码、程序设计语言来描述。
3.程序的定义：当一个算法使用计算机程序设计语言描述时，就是程序。
4.算法4个重要特征和涵义：
1）正确性：算法的执行结果应当满足预先规定的功能和性能要求。
2）简明性：算法应思路清晰、层次分明、容易理解、利于编码和调试。
3）效率：算法应有效使用存储空间，并具有高效的时间效率。
4）最优性：算法的执行时间已达到求解该类问题所需时间的下限。
5.可靠性的定义：一个可靠的程序应当能在正常情况下正确地工作，而在异常情况下，亦能做出适当处理，这就是程序的可靠性。
6.影响程序运行时间的因素：
1）程序所依赖的算法（根本的、起决定性作用）。
2）问题规模和输入数据（输入、输出、数值大小和状态）。
3）计算机系统性能（硬件系统性能（CPU速度）和软件系统性能（操作系统、编译器））。
7.最常见的多项式时间算法的渐进时间复杂度之间的关系：O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)
最常见的指数时间算法的渐进时间复杂度之间的关系：O(2ⁿ)<O(n!)< O(nⁿ)
8.分治法的基本思想：分解、求解、再合并
9.分治法的4个特征：
1）该问题的规模缩小到一定程度可以容易地解决。
2）该问题可以分解为若干个规模较小的相同问题。
3）利用该问题分解出的子问题的解可以合并为该问题的解。
4）该问题所分解出的每个子问题是相互独立的。
10.所谓最优化问题指这样一类问题，问题给定默写约束条件，满足这些约束条件的问题称为可行解，使目标函数函数取取最大（或最小）值的可行解称为最优解。
11.贪心法是一种求解最优化问题的算法设计策略。
12.贪心算法求解问题具有两个性质：贪心选择性质和最优子结构性质。
13.最优子结构特性：当一个问题的最优解中包含了子问题的最优解时，则称该问题具有最优子结构特性。
14.剪枝函数包括约束函数和限界函数：约束函数可以避免无谓地搜索那些已知不含答案状态的子树；最优化问题可以使用限界函数，剪去那些不可能包含最优答案结点的子树。
15.回溯法定义：使用剪枝函数的深度优先生产状态空间树中结点的求解方法称为回溯法。
16.分支限界法定义：采用广度优先产生状态空间树的结点，并使用剪枝函数的方法称为分支限界法。
17.分支限界法分为：FIFO分支限界法、LIFO分支限界法、LC分支限界法三种形式。
18.易处理问题定义：将能在多项式时间内求解的问题看作易处理问题。
难处理问题定义：将至今尚未找到多项式时间算法求解的问题视为难处理问题。
判定问题定义：一个只要求产生“0”或“1”作为输出的问题视为判定问题。