研究生课程 算法分析笔记
算法分析有四大经典的思想，分治法、贪心法、动态规划，最后一个是回溯法和分支限界法，后面会针对性都出一篇博客总结。这篇博文先总结一下除了四大算法之外的，杂七杂八的笔记。
复杂度分析
复杂度分析涉及一些比较麻烦的符号，主要是五个：上界符号 O，下界符号 Ω，准确界 Θ，非紧上界 o，非紧下界 ω，不过感觉主要用的多的还是上界符号 O，理解一个，其他的符号也就好理解了。详细介绍如下。
运行时间上界
定义：对于要研究的函数 f(n)，我们尝试找到这样一个函数 g(n)，若存在自然数 n0 和正的常数 c，使得对所有的 n≥n0，都有
含义：f(n) 的增长最多像 g(n) 那样快。称 O(g(n)) 是 f(n) 的上界。
举例：若 T(n)=12.5n2，那么可以取 c=13， 令 g(n)=n2, 有 T(n)<=cg(n) ，找到一个上界，那么 O(g(n))=O(n2)。 注意这里其实如果取 g(n)=n3 也是可以的。
运行时间下界
定义：和上界符号 O 正好相反，有
含义：f(n) 的增长最少像 g(n) 那样快。称 O(g(n)) 是 f(n) 的下界。
举例：若 T(n)=n2+435n+24，那么可以取 c=1， 令 g(n)=n2, 有 T(n)>=cg(n) ，找到一个下界，那么 Ω(g(n))=Ω(n2).
运行时间的准确界
对于函数 f(n)，我们想找到这样的函数 g(n)，对于自然数 n0 和常数 0≤c1≤c2，都有
非紧上界
用 o 表示，和上界记号 O 很像，但是无法取等于号，即 f(n)<cg(n)
非紧下界
用 ω 表示，和下界记号 Ω 很像，但是无法取等于号，即 f(n)>cg(n)
求解递归方程
用分治法之类的方法，常常要分析递归方程的复杂度，如汉诺塔问题、斐波那契数列问题等，需要从递归方程的复杂度中计算出算法整体的复杂度。这里介绍了三种方法，用生成函数，特征方程和递推的方法。
讲的不是很详细，全当考试复习的笔记了。
用生成函数求解
构造生成函数 -> 求解生成函数 -> 得到递归方程表达式
用特征方程求解
k 阶常系数线性 齐次 递归方程
- 构造特征方程，解方程得到 n 个根（可能有 ri
个重根）
- 如三个根可能是 q1=q2=1,q3=3
- 待定系数法的通解表达式
- 那么解的形式为 f(n)=(c1+c2n)qn1+c3qn3
- 用初始条件解出系数
- 根据 f(0)=1,f(1)=2,f(2)=7 的初始条件算出 c1,c2,c3
k 阶常系数线性 非齐次 递归方程
- 非齐次通解 = 齐次方程的通解 + 非齐次的特解
- 齐次方程的通解求解，和上面一样
- 非齐次的特解，要假设（要根据 g(n) 的次数来假设）后带入原方程求解系数 Ai。
- 待定系数（系数是 ci）法求解非齐次方程的通解
用递推方法求解
- 一个个带入进去
- 技巧：换名，比如分析二分查找的复杂度时，令 g(k)=f(2k)=f(n)
NP 完全问题
NP 完全问题，属于计算复杂度理论，可以参考 wiki 上的 计算复杂性理论。
四个问题
能在以多项式时间内解决的问题是 P 类问题（Polynomial Problem）。易知，所有的易解问题都是 P 类问题。
能在多项式时间内验证的问题是 NP 问题（Non-deterministic polynomial Problem），但是一般还找不到多项式时间的算法解决此类问题。
一个 NP 类问题的重要的子类，叫做 NPC 问题（NP Complete Problem），或 NP 完全问题。定义如下：如果所有的 NP 问题都能在多项式时间内规约（reduction）成某个 NP 问题，那么这个 NP 问题就是个 NPC 问题。
若 P != NP，这三类问题的关系如下图：
很多复杂的问题都是 NP 问题，即很容易给出一个判定，但是找不到多项式的算法来解决这个问题，但是又无法得到知否能够得出多项式时间的解法。考虑 一个 NPC 问题如果能在多项式时间内得到解决，那么 NP 类中的每个问题都可以在多项式时间内规约到该问题，也就相应的都可以在多项式时间内得到解决。即 P = NP 成立！意思就是解决了一个 NPC 问题，所有的 NP 问题就都解决了。
然而究竟 P = NP 是否正确，始终悬而未决。参考维基百科 NP 完全 词条。
除此之外，还有一种 NP 难问题（Non-deterministic Polynomial hard Problem，NP-hard Problem），是比 NP 问题更难的问题，因为都不知道能不能在多项式时间内 验证一个解的正确性，更不用提解决了。所以 NP-hard 至少和 NPC 问题一样难。
这四类问题的关系如下图：
那么 NPC 问题和 NP-hard 问题的关系是什么呢？
满足下面两个条件的问题就是 NPC 问题。首先，它得是一个 NP 问题；然后，所有的 NP 问题都可以约化到它。NP-Hard 问题是这样一种问题，它满足 NPC 问题定义的第二条但不一定要满足第一条（就是说，NP-Hard 问题要比NPC问题的范围广）。
约化(Reducibility)：一个问题A可以约化为问题B的含义即是，可以用问题B的解法解决问题A，问题A可约化为问题B”有一个重要的直观意义：B的时间复杂度高于或者等于A的时间复杂度。
图灵机
图灵机的四个组成部分：
- 纸袋（tape）：无限长，划分成方格，每个方格都有一个从固定的字母表中选取的字母
- 读写头（head）：能够在纸袋上进行读和写操作
- 内部状态（state register）：相当于逻辑存储器
- 控制程序（table）：有限大小的指令，根据内部存储和命令进行磁带的读写和移动
停机问题：逻辑数学中可计算理论的一个问题。通俗的说，就是判断任意一个程序是否能够在有限的时间之内结束运行的问题。停机问题在图灵机上是不可判定的。
和停机问题类似的一个不可判定的悖论是理发师悖论：村子里有个理发师，这个理发师有条原则是，对于村里所有人，若且唯若这个人不自己理发，理发师就给这个人理发。如果这个人自己理发，理发师就不给这个人理发。无法回答的问题是，理发师给自己理发么？