对于算法一些概念的小总结
本学期上了算法设计与分析这门课程，简单的对其中的一些概念进行一下总结。基本都是我的一些宏观上的理解。
时间复杂度，空间复杂度是算法重要的衡量标准。有很多算法问题都是多项式时间无法解决的。在算法面试中，如果你写出了O(n^2)的算法，基本都是可以进行优化的。一般认为，一个算法的空间复杂度不会超过其时间复杂度。我个人的理解是：如果产生这么多的空间复杂度，那么时间最少也是与空间复杂度相同的，比如读入一个A[n][n]的数组，读取它也必须得O(n^2)的时间。我们首先可以讨论一下算法和程序的区别，很久之前就看到程序是这样定义的：程序=算法+数据结构。对于算法来说，它是解决一个问题的方法和过程，一个输入对应其一个输出。算法是给人看到。程序则是利用特定的计算机语言，来描述一个算法，是给机器看的。
理解渐进表达式
一般采用渐进表达式来衡量算法的时间复杂度和空间复杂度，忽略了常数。首先要理解，指数增长是极其恐怖的，在算法运行时间中应当尽量避免。很多算法都可以用指数时间的穷举算法来实现，但是否存在多项式时间算法是计算机科学的核心问题。
在下面的讨论中，对所有n，f(n) >= 0，g(n) >= 0。
（1）渐近上界记号大O
O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n>=n0有：0 <= f(n) <= cg(n) }
（2）渐近下界记号 Ω
Ω(g(n)) = { f(n) | 存在正常数c和n0使得对所有n>=n0有：0 <= cg(n) <= f(n) }
（3）紧渐近界记号Θ
Θ(g(n)) = { f(n) | 存在正常数c1,c2和n0使得对所有n>=n0有：c1g(n) <= f(n) <= c2g(n) }
例如： f(n)= 32n2+ 17n + 32.
f(n)属于O(n2),O(n3),Ω(n2),Ω(n),and Θ(n2).
f(n)不属于 O(n),Ω(n3),Θ(n),or Θ(n3).
对于非渐进记号，用小写符号表示，式子的<=, >= 变为< >。
理解递归表达式的求解
递归是我们算法中非常重要的一个概念与方法。在很多算法中，比如：分治，对于子问题的求解一般用递归来求解。要会求解递归表达式，从而得到算法的时间复杂度。
对于递归表达式的求解，有递归树求解方法，但是最简单的方法是利用主方法进行求解。
例如归并排序：将一个有n规模的问题分成n/2。得到递归表达式：T(n)= 2T(n/2) +Θ(n)
先介绍一个主方法：
T(n)= aT(n/b) + f(n)，分三种情况：
则，归并排序的时间复杂度利用主方法进行求解，符合case2。则其时间复杂度为：O(nlgn)。注意：在算法中：lg=log2(以2为底)。
贪心算法(Greedy)/分治算法(Divide-and-conquer)/动态规划(Dynamic Programming)
贪心/分治/DP是常用的算法。下边我简单的说一下对于这三种算法的简单理解：
贪心算法：
顾名思义，就是选择当前最好的选择。其关键是贪心的策略的选择。比如任务调度问题，
此问题是求在规定的时间内，可最多安排的任务数。可利用贪心算法来求解，按照任务的完成时间进行排序，贪心策略就是按照任务的完成时间从小到大进行安排，同时要保证任务不冲突。
此问题用贪心是可以得到最优解的，可以利用反证法证明此贪心策略的有效性。假设利用此贪心策略得到的解S不是最优，假设S*最优，然后依次比较任务，假设第r+1个任务不同，这时我们会发现，利用此贪心策略，是可以将S中的r+1任务来替换S*中的J+1任务的，这时S*依然是最优的，此时两者的r+1任务也相同了。所以这与我们的假设只有r+1任务不同矛盾，证明了从贪心策略。
Other greedy algorithms. Kruskal,Prim, Dijkstra,Huffman, …
分治算法：
分治算法的思想就是将问题划分为规模较小的子问题，对每个问题进行递归求解，然后合并子问题。列出递归表达式。很多算法，比如归并排序、快速排序都是利用了分治的思想。
这里就不对分治算法就不展开进行分析了。
动态规划DP
动态规划与分治算法最大的区别就是：动态规划存在大量的子问题，对子问题的重复求解，浪费了大量的时间。动态规划就是通过记录子问题的解或者从底向上求解递归表达式，从而避免重叠子问题，是一种以空间换时间的算法。
动态规划算法的求解步骤就是：
1. 定义子问题；
2.写出递归表达式，和边界条件。
3. 从底向上求解递归表达式。
下边，利用动态规划的经典问题：背包问题进行分析：
背包容量：11，求能装的最大价值的物品。
1. 定义子问题：
OPT(i,w):代表前i个物品在背包容量为w时的最大价值。
2. 定义递归表达式：
3. 从底向上求解：
利用从底向上求解，或者递归求解，利用一个二维数组记录每一个子问题的解。最后一个[n][w]就是背包问题的解。
注意：此算法的时间复杂度为O(nw)。这是一个伪多项式时间，可能输入不是多项式的。
多项式规约/NP/EXP/NPC/NPC问题证明/NP-hard/近似算法
这里再简单介绍一个标题的这些概念。
多项式规约：是指经过多项式个步骤将一个问题A转化为另一个问题B，多项式调用解决B问题的算法可以解决问题A。多项式规约，是证明一个问题是NPC的基础。
NP：NP问题的定义是：一个算法存在多项式检验算法，也就是给定一个解可以验证其是否正确。（多项式时间是属于NP的）
EXP：存在指数时间算法。
NPC：现在没有验证，问题是否存在一个多项式算法。
NP-EXP-NPC问题都是对于判断问题而言的（算法结果是：YES,NO）。
证明一个问题是否是NPC问题：
1. 改问题是NP问题；
2.存在一个一致的NPC问题可以多项式规约到此问题。
如果该问题不是NP的，但可以进行多项式规约，则此问题是NP-hard。
电路满足问题，3满足问题，点覆盖问题，集合覆盖，独立集问题。。。都是NPC问题，NPC问题都是可以进行互相规约的。
近似算法：用来解决NP问题，与最优解存在p倍关系。