基本概念
- 一个计算是能够在某种计算装置上机械地执行的一个操作序列。
- 输入规模：计算问题的输入数据所占用存储单元的数量n。
- 时间复杂度：计算过程执行的计算规则的个数表示成输入规模n的函数f(n)。
- 空间复杂度：计算过程使用的不同存储单元的个数表示成输入规模n的函数g(n)。
- P：存在多项式时间复杂度的确定型图灵机的计算问题构成的集合。
- NP：存在多项式时间复杂度的非确定型图灵机的计算问题构成的集合。
什么是算法
算法是一个满足下列条件的计算：
- 有穷性：有限步骤内必须停止。
- 确定性：每一步都是严格定义和确定的动作。
- 能行性：每一个动作都能够被精确地机械执行。
- 输入：有一个满足给定约束条件的输入。
- 输出：给出满足给定输出条件的结果。
证明算法正确性
循环不变量方法
- 循环不变量P：在算法所操作的数据或数据结构上定义一个关键性址P
- 初始：证明循环开始前，循环不变量P成立
- 循环不变：证明循环体每执行一次之后，循环不变量P仍然成立
- 终止：证明循环结束后，循环不变量P确保算法（操作结果）的正确性
算法设计的基本技术
分治算法
设计过程
- 问题划分：将问题划分成一系列（相似）子问题
- 递归求解：递归地调用算法自身求解子问题
- 合并：将子问题的解合并成原问题的解
分析过程
- 首先分别分析设计过程的每个步骤的复杂性
- 然后建立关于复杂性的递归方程
- 最后求解递归方程得到复杂性
动态规划算法
原理：采用分治思想求解子问题时，如果子问题之间不是互相独立的，就会导致子问题被重复求解，效率低下。动态规划算法采用分治思想求解子问题，并利用子问题之间的关联特性来提高计算效率。它从规模最小的子问题开始，自底向上地求解各个子问题，并将子问题的解存储在一个数据结构中，在需要重复求解子问题时通过查询数据结构直接获得该子问题的解。
- 优化子结构：证明优化问题的解可以通过它的一系列子问题的解构造得到。
- 重叠子问题：证明根据优化问题的优化子结构直接采用分治方法求解该问题将导致某些子问题被重复求解。
- 递归定义最优解的代价：根据优化子结构将规模较大的子问题的解通过恰当的数学运算表达式表达成规模较小的子问题的解。由此建立解的递归方程，同时给出递归方程的初始值。
- 自底向上计算解的代价：根据上一个步骤得到的递归方程及其初始化条件，设计数据结构和子问题的计算次序，确保该次序中处理规模较大的子问题时，递归方程中涉及的规模较小的子问题的解均已被计算出来存储在数据结构中。
- 构造最优解：利用前一步获取的构造最优解的信息，将问题的解构造出来。
贪心算法
原理：贪心算法处理优化问题时，在每个步骤总选择当前最佳策略，即希望通过局部优化达到全局优化的效果。一般而言，贪心算法仅获得问题的一个可行解。贪心算法仅搜索了问题的部分解空间，放弃搜索整个解空间，提高了算法的效率。贪心算法也可能获得问题的优化解。
贪心选择性：如果一个优化问题的贪心选择必然出现在问题的一个最优解中，则称该问题具有贪心选择性。
贪心子结构：如果一个优化问题的贪心选择与贪心选择后剩下的子问题的解一起构成问题的一个优化解，则称该问题具有贪心子结构。
平摊分析技术
-
聚集方法：聚集方法直接计算得到数据结构D上的操作序列的时间复杂度上界T(n)，然后将T(n)平摊到每个操作上，进而为每个操作分配相同的平摊代价T(n)/n。
-
会计方法：会计方法在分析操作序列的复杂度上界时，为操作序列中不同类别的操作分配不同的平摊代价。每个操作的平摊代价可能比实际代价高，也可能低。当操作的平摊代价比实际高时，将代价余额存储在操作的数据对象上，反之，当平摊代价比实际低时，由平摊代价与操作的数据对象上的代价余额一起支付实际代价。会计方法的核心在于定义各类操作的平摊代价，使得在任意合理的操作序列下，数据结构D中所有数据对象的代价余额之和总是非负的；进而确保平摊代价的总和是实际代价总和的上界。
-
势能方法：势能方法也为数据结构D上不同的操作分配不同的平摊代价。当操作的平摊代价高于该操作的实际代价时，势能方法将代价余额关联到数据结构上，而不是像会计方法那样将代价余额关联到操作涉及的具体数据对象上。数据结构D上存储的总的代价余额就是D的势能。当操作的平摊代价低于实际代价时，数据结构的势能同平摊代价一起支付操作的实际代价。实际应用势能方法时，通常使初始状态的势能为0，且经过任意操作序列后势能始终大于等于零。势能方法的关键是势能函数的定义，不同的势能函数为各个操作定义了不同的平摊代价，也就产生了操作序列时间复杂度的不同上界。
作者：Wray Zheng
原文：http://www.codebelief.com/article/2017/06/design-and-analysis-of-algorithm-summary/
