Question

Algorithm Analysis

演算法可以切开为两个部分：演算法设计、演算法分析。

演算法设计：制造演算法。演算法设计目前已经有一些经典手法，例如 Dynamic Programming、Greedy Method 等等。

演算法分析：针对特定演算法，精确计量时间複杂度和空间複杂度。演算法分析会用到很多数学知识。下面这两本书内容很详细，我想应该不太需要再重複整理一遍。

http://aofa.cs.princeton.edu/home/

http://soltys.cs.csuci.edu/blog/?page_id=404

大家加油吧！

以下章节是随兴所至谈天说地，参考看看就好。

时间複杂度

想要描述一个演算法执行速度有多快，直觉的方式是测量演算法计算时间。但是由于执行时间深受机器规格与实作方式影响，难以放诸四海皆准，因此学术上倾向于统计演算法步骤数目。

现在大家採用的方式是统计演算法步骤数目。但是由于每个步骤的执行时间都不一样，加减较快、乘除较慢，因此这也是不那麽准确的方式。更何况，实际上的运作过程，是将程式码编译成机器码，然后实施 Instruction Pipeline。指令数量、演算法的步骤数目，两者根本没有绝对关係。

然而目前也尚未找到更好的方式，于是大家将就著用。

时间複杂度标记法

时间複杂度的标记法，是几十年前的数学家发明的方式：大写的英文字母 O 函数，代表演算法执行步骤数目上限；大写的希腊字母Ω函数，代表下限；大写的希腊字母Θ函数，代表同时满足上限与下限（不多不少刚刚好）。这些都是假设 n 足够大、甚至无限大。又由于 n 足够大，所以我们只需比较函数的最高次方项。另外我们省略了最高次方项的係数。

因为省略了很多东西，所以时间複杂度往往无法正确反映演算法的快慢。例如 n=100 的情况下，有可能 O(n^3) 的演算法表现的比 O(n^2) 好。例如两个同为 O(n) 的演算法可能不一样快，n 大时甲快、n 小时乙快。

时间複杂度标记法，也完全忽略了 I/O 处理和记忆体管理的问题。要是资料结构複杂一点、庞大一点，读取资料就会变慢。

时间複杂度标记法，也完全忽略了程式语言特性和平台特性。平平同一个演算法，用 C 写执行较快，用 Java、Python 写执行较慢。因为后者的记忆体管理机制更加複杂，而且牵扯到系统运作架构。

时间複杂度标记法再怎麽不可靠，也比不上实作的不可靠。平平同一个演算法，不同人写出来的程式码，执行效率都不一样，相差十倍都有可能。

然而目前也尚未找到更好的方式，于是大家将就著用。

输入资料

输入资料常常影响时间複杂度。举例来说，当输入资料已经排序完毕，此时实施排序演算法，只需检查一遍输入资料，即可发现根本无须排序，直接结束演算法，时间複杂度 O(N)！

当输入资料很整齐，那我们可以得到最佳或最坏的时间複杂度为多少；当输入资料很乱，那我们可以得到平均的时间複杂度多少。例如 Quicksort，最佳 O(N)，平均 O(N*logN)，最差 O(N^2)。

另外还想强调一件事：最佳、平均、最坏跟Ω、Θ、O 没有关係，不知道为什麽很多人觉得它们是对应的。

Smoothed Analysis 则是分析输入资料有多少机率是整齐的、多少机率是乱的。

计算步骤

演算法的步骤数目不是固定的时候，可以使用 Probabilistic Analysis 和 Amortized Analysis 和 Competitive Analysis。

当今电脑计算能力的极限

也许各位已经听闻过当今七大数学难题之一“P=NP 问题”。目前的电脑运算能力其实差强人意，绝大多数的问题都没办法快速地求解。就算找来大量电脑实施平行计算，依然没办法快速地求解。

然而，现代人类对于电脑有著神祇般的依赖，各种日常生活问题都祈望电脑能够帮上忙。于是近似演算法出现了，用来求得一个马马虎虎差不多的答案。

计算方式

现今流行的计算机，是由逻辑电路组成，使用 AND 与 OR，兜出加减乘除四则运算，运算能力差强人意。遇到 NP 问题，就得耗费大量计算时间，无法迅速求得答案。

除了逻辑电路以外，其实还有其他方式，诸如 Quantum Computing 、 Optical Computing 、 DNA Computing 。这些计算方式，运算能力极强，计算时间极短。之所以不流行，是因为计算难以控制、机器难以量产。

一旦新的计算方式开始流行，我们现在习惯使用的时间複杂度分析方式，只能作古了。

P versus NP

示意图

P 问题

用多项式时间演算法能够计算答案的问题。

“找出一群数字当中最大的数字”是 P 问题。

P 的全名是 Polynomial time，定义源自于“自动机理论”，颇複杂，此处省略之。通常以“P”表示所有 P 问题构成的集合。

NP 问题

用指数时间演算法能够计算答案的问题，同时，用多项式时间演算法能够验证答案的问题。

由于 P 问题也可以改用指数时间演算法计算答案、当然可以用多项式时间验证答案，故 P 问题都属于 NP 问题。

“找出一张图的一条 Hamilton Path”是 NP 问题。

计算答案：
穷举所有可能的路线，一条一条验证。
是指数时间演算法。

验证答案：
给定一条可能的路线，就照著路线走，看看能不能走到每一点。
是多项式时间演算法。

“找出一张图成本最小的那条 Hamilton Path”不是 NP 问题。

计算答案：
穷举所有可能的路线，一条一条验证。
是指数时间演算法。

验证答案：
就算给定一条可能的路线，
还是必须穷举所有路线，一条一条验证，才知道哪条路线成本最少。
是指数时间演算法。

值得一提的是，每一个 NP 问题，都可以设计出多项式时间演算法，转换成另一个 NP 问题。换句话说，所有 NP 问题都可以用多项式时间演算法彼此转换。

NP 的全名是 Non-deterministic Polynomial time，定义源自于“自动机理论”，颇複杂，此处省略之。通常以“NP”表示所有 NP 问题构成的集合。

NP-complete 问题

所有 NP 问题当中，最具代表性、层次最高、最难的问题。

NP-complete 问题的各种特例，涵盖了所有 NP 问题。只要有办法解决 NP-complete 问题，就有办法解决 NP 问题。

各个 NP-complete 问题都等价、都一样难，可以用多项式时间演算法彼此转换。现今已经找出上百个 NP-complete 问题了。

Complete 的意义为：能够代表整个集合的子集合。举例来说，它就像是一个线性空间（linear space）的基底（basis）。

“判断一张图是否存在 Hamilton Path”已被证明是 NP-complete 问题。

NP-hard 问题

用多项式时间演算法转换 NP 问题所得到的问题，同时，必须是跟 NP-complete 问题一样难、还要难的问题。

NP-hard 问题可能是：甲、NP-complete 问题（是 NP 问题），乙、超出 NP 问题的複杂度，是更难的问题。

“找出一张图成本最小的 Hamilton Path”是 NP-hard 问题。

由“找出一张图的一条 Hamilton Path”这个 NP 问题，
用多项式时间把每条边加上成本而得。
而且“找出一张图成本最小的 Hamilton Path”至少比 NP-complete 问题还难。

P = NP ?

这是计算机科学的一个悬案。大意是说：到底 NP 问题能不能用多项式时间演算法解决呢？如果可以的话，那麽 NP 问题就都变成了 P 问题了。这意味著有一些花上几十年几百年算不出答案的问题，变得可以在几分几秒内计算完毕、得到答案。

有一个解决这个悬案的方向是：尝试发明一个多项式时间演算法，解决某一个 NP-complete 问题。接著我们可以将此 NP-complete 问题进行特例化得到所有 NP 问题，如此一来，所有 NP 问题都可以用此多项式时间演算法算出答案了。

很多人声称自己已经成功证明了，但是至今还没有一个让所有人都信服的证明：

http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

介于 P 与 NP-complete 之间的问题

http://cstheory.stackexchange.com/questions/79/

为什麽要学校老师要教 NP？

台湾的演算法课程，都是直接抄旧书，特别强调 NP-Complete，特别强调问题之间的转换。不过职场上几乎不会用到这些知识。学术上要解决 P = NP 问题，也不会用到这些知识。

现在比较新的教学资料，都是直接介绍多项式时间和指数时间的差异，而不是去介绍 P、NP、NP-hard 到底谁包含谁。

时间複杂度下限

所有的演算法教科书，只要是介绍演算法，一定提及时间複杂度上限 O 函数，鲜少提及时间複杂度下限Ω函数。例如最短路径问题，Dijkstra 演算法是 O(N^2)，Floyd-Warshall 演算法有三个迴圈是 O(N^3)，大家肯定耳熟能详。但是最短路径问题的时间複杂度至少是多少呢？作者没讲！原因是下限非常难以证明。

想要证明上限，只需想出一个时间複杂度更低（更快）的演算法，便得到了新的上限、更低一点的上限。想要证明下限，却必须穷举所有可能的演算法，证明没有任何时间複杂度更低（更快）的演算法，才能得到新的下限、更高一点的下限。“列举一个”与“穷举全部”的差别，这就是困难所在之处。

目前只有少数几个问题，内容简单、具有严格限制的问题，可以明确证明下限：

一个经典的例子是“两两比较的排序演算法”，最少必须比较 NlogN 次，时间複杂度下限是Ω(NlogN)。证明方式是用树状图展开所有可能性，树的末端节点共 N!个，树的高度至多是 logN! ≤ logNᴺ = NlogN。

然而，排序演算法还有 counting sort、hashing 这些可能性，不一定只能两两比较。限制成两两比较，非常不切实际。

另一个经典的例子是“求出一群点的凸包”，化成两两比较的排序问题，得到时间複杂度下限是Ω(NlogN)。

然而，如果解除了两两比较的限制，便有时间複杂度更低的演算法。设定这种限制，非常不切实际。

例子少得可怜。现况就是如此。

P = NP 问题的困难之处，在于证明时间複杂度下限。必须证明 NP 问题的时间複杂度下限，到底是和 P 一样是多项式时间、或者是和 NP-Complete 一样是指数时间。超级难的！

另一种策略是改为证明 NP 问题的时间複杂度上限。只要找到任何一个多项式时间演算法解决任何一个 NP-complete 问题（所有 NP 问题当中最複杂的问题），就能确确实实的降低所有 NP 问题的上限。不过目前也没有人找到这样一个演算法。

Algorithm Class

Offline Algorithm / Online Algorithm

“离线演算法”是一口气输入所有资料之后，才能开始运行的演算法。例如 Bubble Sort。

“在线演算法”是不需等待所有资料到达，就可以分时分段处理输入的演算法。例如 Insertion Sort。

有些“在线演算法”甚至可以即时提供目前所有输入的正确输出。例如 Insertion Sort。

Static Algorithm / Dynamic Algorithm

“静态演算法”是无法随时修改、增加、减少原本的输入资料，无法随时查询输出的演算法。例如 Dijkstra's Algorithm。

“动态演算法”是可以随时修改、增加、减少原本的输入资料，可以随时查询输出的演算法。例如 Binary Search Tree。

Exact Algorithm / Approximation Algorithm

“精确演算法”是计算结果绝对正确的演算法。

“近似演算法”是计算结果拥有误差的演算法。

有许多问题无法快速计算正确答案。为了追求速度，就会设计“近似演算法”。

Complexity Class

Approximation Algorithm

APX   有多项式时间演算法
      近似到 MINOPT*n  或者 MAXOPT*n  对于一个 n

PTAS  有伪多项式时间演算法 (n 的多项式，ε视作定值)
      近似到 MINOPT*(1+ε) 或者 MAXOPT*(1-ε) 对于所有ε

FPTAS 有多项式时间演算法 (1/ε和 n 两种变数构成的多项式)
      近似到 MINOPT*(1+ε) 或者 MAXOPT*(1-ε) 对于所有ε

CLRS 只有教到 APX (Vertex-Cover 与 Euclidean-TSP 与 Set-Cover 的近似演算法)

Randomized Algorithm

BPP   有多项式时间演算法
      出错机率至多 1/3，正确机率至少 2/3。
      执行 k 次，投票表决，让出错机率降为 (1/3)^k

RP    有多项式时间演算法
      当答案为 Yes，有 1/2 机率答错。
      当答案为 No，绝对不会答错。
      执行 k 次，投票表决，让出错机率降为 (1/2)^k

ZPP   有多项式时间演算法
      要嘛回答正确答案，要嘛不知道答案，机率各 1/2。

CLRS 没有教到

一、不会影响答案。

二、避免偏颇答案。

以随机的运算数值、计算顺序，取代不明的、糟糕的输入数值、输入顺序。

一、不清楚输入资料的分布情况，无从分析 average case 的时间複杂度──此时可以用随机的计算顺序，将时间複杂度的期望值，姑且当作是 average case 的时间複杂度。

二、十分清楚输入资料的分布情况，而且输入资料接近 worst case──此时可以用随机的计算顺序破坏 worst case，有很大机率能趋吉避凶，减少计算时间；但是也有一定机率会弄巧成拙，增加计算时间。

随机演算法必须运用机率来分析时间複杂度。一种计算顺序，对应一个时间複杂度；考虑每一种计算顺序的出现机率，求得时间複杂度的期望值。

Complexity Notation

α(N)

α(N) 是 Ackermann function f(N,N) 的反函数。

Õ

符号读做 tlide O，意义读做 soft O，用来隐藏 polylog。

Õ(g(x)) = O( g(x) * logᵏg(x) ) = O( g(x) * polylog g(x) )
polylog(x) = logᵏx

log*

符号读做 log star，意义读做 iterated logarithm。

不断算 log，直到变成 1，总共需要的 log 次数。

Intractable Problem

Intractable Problem

难题，难以设计快速的演算法。实务上的解法有：

一、最佳化。请参考“ Optimization ”。

二、状态空间搜寻。请参考“ State ”。

三、类神经网路。请参考“ Classification ”。

以下做了简单分类。注意到这不是公认的分类方式。

Picking

Boolean Satisfiability Problem：设定真假值，使逻辑计算式结果为真。

Partitioning

Partition Problem：一群数字，分成两群，让两群总和一样多。
Integer Factorization：一个数字乘积，拆散成数字。

Packing

Packing Problem：使用特定几何图形，互不重叠，尽量填满空间。
Knapsack Problem：一个容器，一堆物品，尽量放入所有物品。
Bin Packing Problem：一堆容器，一堆物品，使用最少容器，放入所有物品。
Container Loading Problem：3D 长方体堆积。
Box Stacking Problem：3D 无盖箱子堆叠。

Covering

Covering Problem：使用特定几何图形，覆盖空间，数量尽量少。
Set Cover Problem：一堆集合，各自包含某些元素。用最少个集合，涵盖所有元素。
Steiner Tree Problem：使用线条，连接所有地点，长度尽量短。
Facility Location Problem：选定 P 点，连接所有地点，成本尽量小。

若以“ Minimum Cost Flow ”为模型，则必须要有流量放大的机制。

Routing

Hamilton Circuit：拜访所有景点的最短路线。
Vehicle Routing Problem：从起点出发多次，拜访所有景点的最短路线。
Chess Problem：给定棋盘盘面，找到赢棋下法。

Scheduling

http://www.informatik.uni-osnabrueck.de/knust/class/

工厂进行生产制造、规划最佳流程。

open shop：每个工作在每一台机器都要做一次，随便你用什麽顺序做。
job shop：每个工作已经规定好执行机器的顺序。
flow shop：每个工作所规定的执行机器顺序都完全一样。

Graph Coloring：地图相邻区块填入不同颜色，颜色种类尽量少。

UVa 12228 ICPC 7827