算法笔记 - jwyx/ForFun GitHub Wiki
Credit
黑书
http://www.cnblogs.com/Creator/archive/2011/05/21/2053033.html
算法分析
只关心问题规模扩大时时空开销的增长情况
问题模型：n为输入问题的规模，基本操作为一个运行时间不依赖于操作数的操作
基本操作数的选择反映了对问题主要矛盾的认识
在实际问题中，对空间复杂度常用非渐进形式的精确表示，因为一点点差异可以引起‘存得下’和‘存不下’的本质区别
不同情况下的运行时间
最好，最差，平均，概率分析和均摊分析
时空辩证关系
时间换空间 e.g. 重复计算
空间换时间 e.g. 预处理
基于的计算模型
最常见的微型计算机，特点是同一时间只能执行一条指令，并且执行的指令是确定的
随机存储RAM模型，特点是可以随机访问存储器
基本算法
枚举
贪心
递归
分治
递推
贪心
思想
每一步总是做出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。
从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
简单，省时，好用
问题
1. 不能保证求得的最后解是最佳的；
2. 不能用来求最大或最小解问题；
3. 只能求满足某些约束条件的可行解的范围
解决
动态规划，回溯算法，分支限界算法
动态规划
思想
将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。
与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。
动态规划算法将问题的解决方案视为一系列决策的结果，与贪婪算法不同的是，在贪婪算法中，每采用一次贪婪准则，便做出一个不可撤回的决策；
而在动态规划算法中，还要考察每个最优决策序列中是否包含一个最优决策子序列，即问题是否具有最优子结构性质。
分治
思想
将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。
将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
步骤
1. 分解，将要解决的问题划分成若干规模较小的同类问题
2. 求解，当子问题划分得足够小时，用较简单的方法解决
3. 合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。
实现
一般使用递归，递归的去分解自身，递归的去解决每一个小问题，然后合并。
也可以使用 循环 进行实现。
回溯
思想
从一条路往前走，能进则进，不能进则退回来，换一条路再试。
也叫试探法，它是一种系统地搜索问题的解的方法。
问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。
先试探性的尝试每一个组合，看看到底通不通，如果不通，则折回去，由最近的一个节点继续向前尝试其他的组合，如此反复。
可以认为回溯算法一个”通用解题法“，这是由他试探性的行为决定的。
步骤
1. 定义一个解空间，它包含问题的解。
2. 利用适于搜索的方法组织解空间。
3. 利用深度优先法搜索解空间。
4. 利用限界函数避免移动到不可能产生解的子空间。
分支限界
步骤
1. 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
2. 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。
3. 在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点将被加入活结点表中。
4. 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。
与回溯的不同
1. 求解目标不同：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，
或是在满足约束条件的解中找出在某种意义下的最优解。
2. 搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。