Question

不积跬步，无以至千里。不积小流，无以成江海。《荀子》

Incremental Method

“递增法”是符合电脑运作特性的方法。电脑执行程式，一次只做一个动作，完成了一件事才做下一件事。当一个问题太大太多时，化整为零、一个一个解决吧！

合抱之木，生于毫末；九层之台，起于累土；千里之行，始于足下。谨以此句与大家共勉。

范例：加总数字

无论电脑再怎麽强，还是得一个一个累加数字。

Memoization

惟事事，乃其有备，有备无患。《书经》

Memoization

“记忆法”是符合电脑运作特性的方法。电脑拥有大量储存空间。只要将计算过的数值，储存于记忆体，往后就能直接使用记忆体储存的资料，不必再浪费时间重複计算一遍。

Memoization（Tabulation）
演算法执行过程之中，即时更新数值，储存于记忆体。
例如堆叠的大小。

Preprocessing（Precalculation）
演算法开始之时，预先计算数值，储存于记忆体。
例如圆周率、字串的长度、质数的表格。

如果要储存大量的、同性质的数值，我们可以将这些数值整理成一个表格（通常是阵列），以方便查阅──称作“查询表 lookup table”。例如质数表便是一个“查询表”。

范例：阵列大小

使用一个变数，记录资料数量，以便迅速地增加资料。

C++程式语言的标准函式库的 stack，事实上也额外隐含了一个变数，记录资料数量。当堆叠塞入资料、弹出资料的时候，也就是呼叫 push 函式、呼叫 pop 函式的时候，就默默更新资料数量。

范例：加总数字

利用一个变数，累计数字的总和。

Enumeration

愚者千虑，必有一得。《史记》

Enumeration

“枚举法”利用了电脑无与伦比的计算速度。找到不确定的变数，枚举所有可能性，逐一判断正确性。

Enumerate
一笔一笔列出所有资料。
对应到程式语言的 for。

Search
浏览所有资料，找出需要的部份。
对应到程式语言的 for 加 if。

收集充分资讯，就能解决问题。

范例：枚举一百个平方数

採用直接法：依序枚举数字 1 到 100；枚举过程当中，将数字平方得到平方数。

Iterative Method

道生一，一生二，二生三，三生万物。《老子》

Iterative Method

繁中“叠代法”、简中“递推法”。不断利用目前求得的数值，再求得新数值。

UVa 997

范例：字串变整数

直觉的方式是递增法。个、十、百、千、万、……，每个位数分别乘上 10 的次方，通通加起来。此处按照高位数到低位数的顺序进行处理，以符合字串的储存顺序。

Recursive Method

易有太极，是生两仪。两仪生四象，四象生八卦。《易传》

Recursive Method

繁中“递迴法”、简中“递归法”。重複运用相同手法，缩减问题范围，直到釐清细节。

UVa 10994 10212 10471 10922

范例：碎形（Fractal）

利用相同手法绘图，绘图范围越来越精细。

图中的碎形称作 Sierpinski triangle。凡是尖端朝上的正三角形，就在当中放置一个尖端朝下的正三角形；放置之后，图形就变得更细腻，范围就变得更小了。

图中的碎形称作 Kosh snowflake。一条边三等分，去除中段，朝外补上两段，形成尖角。

图中的碎形称作 Pythagorean tree。不断绘制正方形、直角三角形，看起来像是一棵茂密的树。

UVa 177 10609

范例：质因数分解（Integer Factorization）

不断抽取出质因数，使数值不断变小，直到成为质因数。

范例：L 形磁砖

有一个边长为 2 的 3 次方的正方形，右上角缺了一角边长为 1 的正方形。现在要以 L 形磁砖贴满这个缺了一角的正方形，该如何贴呢？

巧妙地将一块 L 形磁砖放在中央的位置，就顺利的把正方形切成四个比较小的、亦缺了一角的正方形。接下来只要递迴处理四个小正方形，就解决问题了。

这个问题也可以改成缺口在任意一处，各位可以想想看怎麽解。

UVa 10230

范例：辗转相除法（Euclid's Algorithm）

两个数字轮流相除、求馀数，最后就得到最大公因数（greatest common divisor, gcd）。相信大家小时候都有学过。

我们可以把最大公因数想像成砖块、把两个数字都看成是最大公因数的倍数。

两数相减所得的差值，一定是最大公因数的倍数。更进一步来说，两数相除所得的馀数，一定是最大公因数的倍数。辗转相除法的过程当中，两数自始至终都是最大公因数的倍数。

运用这个性质，我们把两数相除、求馀数，使得原始数字不断缩小，直到得到最大公因数。真是非常巧妙的递归法！

注意到，递推法、递归法，不等于程式语言中的迴圈、递迴。递推法、递归法是分析问题的方法，用来得到计算过程、用来得到演算法。至于编写程式时，我们可以自由地採用迴圈或者递迴。

范例：过桥问题（Bridge and Torch Problem）

月黑风高的夜晚，有一座不长不短的独木桥，只能同时容两人併行。

此时正好有四个寂寞难耐、悲苦凄凉，事实上是穷极无聊的四个人路经此地。他们手边仅带著一支手电筒，想要通过这危险的独木桥。那桥下可是暗潮汹涌，一失足成千古恨，奔流到海不复回。

幸好四人閒閒没事就常走这座桥，对路况简直熟悉到不行，闭著眼睛走都可以，于是乎四人知道自己过桥分别需时 1 分钟、2 分钟、5 分钟、10 分钟。但是不管他们的脚程不可思议的快、莫名其妙的慢，四人都是贪生怕死之徒，手上没有握著手电筒的话，谁都不敢过桥；四人也都是视财如命之徒，就是谁也不想浪费钱，去附近的便利商店买支手电筒，宁可摔到水裡随波逐流环游世界去。

最后他们只好协议说，一次两人同时持手电筒过桥，再请其中一人送回手电筒，没事做的人就在桥边哭爹喊娘等手电筒回来，如此一来四人最终都能够顺利过桥。

两人同时过桥时必须配合走得慢的人的速度，请问全员过桥最快要多久时间？

有一些规矩你是知道的，例如不能把手电筒用丢的丢过河，不能四个人叠罗汉一起过桥，不能把桥拆了做木筏之类的。

题目终于说完了，现在来谈解题手法：

脚程快的人送手电筒回来那是最好的；相对地，脚程慢的人就应该让他留在彼岸不要回来。不管先走后走，人人都还是要过桥，所以先试试看把脚程最慢的人送到对岸吧！

当人数众多，至少四人时，令 A 与 B 是最快与次快，C 与 D 是次慢与最慢。让最慢的两个人过桥主要有两种方式，第一种是 AB 去 A 回、CD 去 B 回，第二种是 AD 去 A 回、AC 去 A 回，至于其它方式所花的时间恰好跟这两种方式一样。採用比较快的那一种方式，让最慢的两个人过桥之后，问题范围就缩小了。

UVa 10037

递推法、递归法，一体两面，同时存在。

递推法与递归法恰好颠倒：递推法是针对已知，逐步累积，直至周全；递归法是针对未知，反覆拆解，直至精确。

递推法是由小到大，递归法是由大到小。

范例：秦九韶演算法（Horner's Rule）

递推法是不断配 x，扩增已知；递归法是不断提 x，减少未知。

a * x^2 + b * x^1 + c

Iterative Method:
{a} * x^2 + b * x^1 + c
{a, *x} * x^1 + b * x^1 + c
{a, *x, +b} * x^1 + c
{a, *x, +b, *x} + c
{a, *x, +b, *x, +c}

Recursive Method:
{a * x^2 + b * x^1 + c}
{a * x^2 + b * x^1}, +c
{a * x^1 + b}, *x, +c
{a * x^1}, +b, *x, +c
{a}, *x, +b, *x, +c

虽然递推法与递归法的推理方向是相反的，但是递推法与递归法的计算方向是一样的，两者都是由小范围算到大范围。

Iterative Method:
a, *x, +b, *x, +c

Recursive Method:
a, *x, +b, *x, +c

UVa 498 10268

范例：爬楼梯

眼前有五阶楼梯，一次只能踏一阶或踏两阶，那麽爬到五阶总共有哪几种踏法？例如(1,1,1,1,1) 是其中一种踏法，(1,2,2) 是另一种踏法。

这个问题可以用递推法，也可以用递归法。

首先採用递推法。试著只爬少少的几阶楼梯，观察一下踏法。

爬到一阶的踏法：很明显的只有一种，(1)。

爬到两阶的踏法：有两种，(1,1) 和(2)。

爬到三阶的踏法：因为一次只能踏一阶或踏两阶，所以只可能从第一阶或从第二阶踏上第三阶。只要综合（爬到一阶的踏法,2) 与（爬到两阶的踏法,1)，就是爬到三阶的踏法。

爬到四阶的踏法：同理，综合（爬到两阶的踏法,2) 与（爬到三阶的踏法,1) 即得。

递推下去，就可求出爬到五阶的踏法。

Forward Iterative Method:
爬到一阶　(1)
爬到两阶　(1,1) (2)
爬到三阶　即是（爬到一阶,2) 与（爬到二阶,1)
　　　　　(1,2)
　　　　　(1,1,1) (2,1)
爬到四阶　即是（爬到二阶,2) 与（爬到三阶,1)
　　　　　(1,1,2) (2,2)
　　　　　(1,2,1) (1,1,1,1) (2,1,1)
爬到五阶　即是（爬到三阶,2) 与（爬到四阶,1)
　　　　　(1,2,2) (1,1,1,2) (2,1,2)
　　　　　(1,1,2,1) (2,2,1) (1,2,1,1) (1,1,1,1,1) (2,1,1,1)

前面是採用上楼梯的顺序进行递推，由第一阶递推到第五阶。也可以採用下楼梯的顺序进行递推，由第五阶递推到第一阶。

Backward Iterative Method:
降到四阶　(1)
降到三阶　(1,1) (2)
降到二阶　即是(2,降到四阶) 与(1,降到三阶)
　　　　　(2,1)
　　　　　(1,1,1) (1,2)
降到一阶　即是(2,降到三阶) 与(1,降到二阶)
　　　　　(2,1,1) (2,2)
　　　　　(1,2,1) (1,1,1,1) (1,1,2)
降到平面　即是(2,降到二阶) 与(1,降到一阶)
　　　　　(2,2,1) (2,1,1,1) (2,1,2)
　　　　　(1,2,1,1) (1,2,2) (1,1,2,1) (1,1,1,1,1) (1,1,1,2)

有一些问题，比如爬楼梯问题，双向都可以递推。数值由小到大的方向称为“正向”或“顺向”（forward），数值由大到小的方向称为“反向”或“逆向”（backward）。

接著採用递归法。由踏出的最后一步开始分析。

要“爬到五阶”，最后一步一定是踏上第五阶。要踏上第五阶，只可能从第四阶和第三阶踏过来，也就是综合（爬到四阶的踏法,1) 与（爬到三阶的踏法,2)。

但是我们尚不知如何“爬到四阶”和“爬到三阶”，所以只好再分别研究“爬到四阶”与“爬到三阶”。不断追究到“爬到一阶”与“爬到两阶”的时候，就能确认答案了！

Forward(?) Recursive Method:
爬到五阶　即是（爬到四阶,1) 与（爬到三阶,2)
爬到四阶　即是（爬到三阶,1) 与（爬到二阶,2)
爬到三阶　即是（爬到二阶,1) 与（爬到一阶,2)
爬到两阶　(2) (1,1)
爬到一阶　(1)

当然也可以双向递归。就不赘述了。

范例：格雷码（Gray Code）

Iterative Method:
GrayCode(n-1) 的每个数字，最高位数加一个 0。
GrayCode(n-1) 的每个数字，高位数与低位数整个颠倒，然后在最高位数加一个 1。
两者衔接起来就是 GrayCode(n)。

Recursive Method:
GrayCode(n) 的每个数字，分成两类。
第一类最高位数是 0，把最高位数拿掉后，即形成 GrayCode(n-1)。
第二类最高位数是 1，把最高位数拿掉后，即形成 GrayCode(n-1)。

也可以用最低位数为主，进行递推、递归，生成顺序不同的 Gray Code。Gray Code 具有循环的特性，有多种递推、递归方式，不分正向与逆向。

Divide and Conquer

凡治众如治寡，分数是也。斗众如斗寡，形名是也。《孙子》

Divide and Conquer

“分治法”，分割问题、各个击破。将一个大问题，分割成许多小问题。如果小问题还是很难，就继续分割成更小的问题，直到问题变得容易解决。

分割出来的小问题，称作“子问题 subproblem”。解决一个问题，等价于解决所有子问题。

用树状图表达原问题与子问题的关係，最好不过！

分治法著重分割问题的方式──要怎麽分割问题，使得子问题简单又好算？各位读者可以藉由本文的范例，体会分割问题的方式。

范例：分解动作

想要学习“从中场带球上篮”，我们可以将此动作分割为“跑步运球”、“跑步收球”、“单手将球放入篮框”等动作，分别学习。每一项动作都熟练之后，组合起来便是带球上篮了。

如果觉得“跑步运球”还是太难，可以更细分成“原地运球”、“走动运球”、“运球时护球”等动作，克服了之后便能够顺利解决“跑步运球”的问题了。

范例：方格法求面积

左边为原问题，右边放大并细分的图是其中一个子问题。

范例：分类数数

左边最大的框框是原问题，将原问题的数字进行分类后再统计，分类后的每一个框框都是一个子问题。

UVa 11038

Recursive Method

在分治法当中，亦得递迴地分割问题，其实就是递归法。

程式码细分为三个阶段：Divide、Conquer、Combine。Divide 阶段是把原问题分割成小问题，Conquer 阶段是解决小问题，Combine 阶段是运用小问题的解答，整理出原问题的解答。

UVa 620 10101 10144 10998

范例：合併排序法（Merge Sort）

Divide 阶段：资料分割成两堆。

Conquer 阶段：两堆资料各自从事 Merge Sort。

Combine 阶段：两堆已排序过的资料，合併成一堆。

范例：快速排序法（Quicksort）

Divide 阶段：挑选一个数字当作基准，把资料分割成左右两堆，使得左堆数字小于基准，右堆数字大于基准，基准数字置于左右两堆中间。

Conquer 阶段：左右两堆资料各自从事 Quicksort。

Combine 阶段：不做任何事。

范例：不重複组合（Combination）

从 N 个人抓 M 个人出来组团，有哪些组合方式呢？

N 个人当中的其中一个人，叫做甲君好了，我们将原问题分割成两种情形：甲君在团中、甲君不在团中。

甲君在团中，演变成剩下 N-1 个人要再抓 M-1 个人出来组团。
甲君不在团中，演变成剩下 N-1 个人仍要抓 M 个人出来组团。

综合这两个子问题的组合方式，就得到答案。

范例：河内塔（Tower of Hanoi）

三根柱子、一叠盘子，盘子大小皆不同（盘子中间还得打个洞，这样盘子才能穿在柱子上）。所有盘子都叠在第一根柱子，大的在下面，小的在上面。现在要将整叠盘子移到第三根柱子，并且保持原来的大小顺序。每次只能搬动一个盘子到别根柱子，而且大的盘子一定要保持在小的盘子下面。

想要移动最大的盘子到第三根柱子，必须先挪开上方整叠盘子到第二根柱子。移动上方整叠盘子，正好与原问题相同、而少了一个盘子，可以视作子问题。

尝试以此子问题解决原问题，解题过程因而简化成三个步骤：一、上方整叠盘子移到第二根柱子；二、最大的盘子移到第三根柱子；三、方才的整叠盘子移到第三根柱子。

Greedy Method

今朝有酒今朝醉，明日愁来明日愁。《罗隐．自遣》

博观而约取，厚积而薄发。《苏轼．稼说送张琥》　

Greedy Method

“贪心法”。以 Incremental Method 或 Iterative Method 制造答案的方法，大致上分为两类：

一、填答案：从没有答案开始，逐步填满答案。
二、改答案：先随便弄个答案，逐步修饰答案。

一、观察问题特徵，拟定一个填答案、改答案的原则。
二、随便挑几个特例，手算一下。
　　如果答案都对，就大胆假设此原则是正确的。
　　（也可以尝试证明此原则必定正确。）
三、实作程式码，把答案算出来。

UVa 120 311 410 514 538 668 757 10148 10201 10249 10366 10382 10440 10602 10716 10718 10982 ICPC 3752 4788

范例：找零钱

你去商店买东西，你掏出了一张一百元，买了一包 23 元的零食。店员须找零钱给你，但是你希望店员找给你的硬币数目越少越好，如此口袋会轻一点。那麽店员会给你几个硬币呢？

填答案的原则是：先找给你面额较高的硬币。

金额越少，找给你的硬币数目也就越少。先找给你面额较高的硬币，金额下降的最多──如此一来，往后找给你的硬币数目就一定是最少了。

注意到：当钱币面额很特别时，这个方法才正确。详情请参考“ Change-Making Problem ”。

范例：文章换行（Word Wrap）

一大段的英文段落，适当的将文章换行，让文字不超过纸张边界，尽量节省纸张空间。

填答案的原则是：字儘量往前挤，挤不下就换行。

范例：骑士周游问题（Knight's Tour）

西洋棋盘上，请找到一条路线，让骑士恰好经过棋盘上每一格各一次。

填答案的原则是：走向出路选择较少的格子。如果遇到出路选择一样多的格子，就走向位于下方的格子。如果又遇到一样低的格子，就走向位于左方的格子。

这种填答案的方式，耗尽死路，保留活路，将来走入死胡同的机会就变少了。有一种“置之死地而后生”的味道。

注意到：这个方法不一定会成功。我们根本无法证明这个方法会成功，只是乍看起来比较容易成功。

我们当下所做的最佳决定，以长远的眼光来看，不一定是最佳决定。儘管贪心法不见得得到正确的、最好的答案，却是个快速得到答案的好方法。

范例：活动选择问题（Activity Selection Problem）

暑假到了，有好多好多有趣的营队可以参加囉！攀岩、潜水、单车环岛团、吉他营、电脑营、……，每个营队都好有趣，好想每个营队都参加──可是却有好多营队的活动期间都互相卡到，没办法同时参加。到底要参加哪些营队活动才好呢？当然是越多种越好！

填答案的原则很简单：优先选择最早结束的活动，就能剩下最多时间来安排其他活动。

仔细分成两种情况进行讨论：一、最早结束的活动，与其他活动的时间不重叠；二、最早结束的活动，与某些活动的时间重叠。

一的状况下，参加最早结束的活动，显然是最理想的──凭空多参加了一个活动，又不耽误到其他活动。

此观念可以用 Recursive Method 诠释：去除最早结束的活动、递迴缩小问题。

二的状况下，最早结束的活动、以及时间与之重叠的活动当中，只能选择其中一个参加。此时参加最早结束的活动，得以剩下比较多的时间，仍是最理想的。

此观念可以用 Recursive Method 诠释：去除最早结束的活动、去除因而无法参加的活动，递迴缩小问题。

填答案的原则是：所有活动按照结束时间排序，依序参加活动。如果时间允许就参加，如果时间衝突就不参加。

UVa 10020 ICPC 4328 5105

范例：函数的区域最小值

改答案的原则是：一开始 x 随意设定一个数值，例如设定 x = 0。微调 x 值，并且计算 f(x)──如果 f(x) 减少，就更新 x；如果 f(x) 没减少，就不更新 x。不断修改 x 值，最后就到达区域最小值。

范例：交换相邻数字的排序法

改答案的原则是：每当发现相邻两个数字，左边数字大于右边数字，两个数字就交换位置。

不断交换位置，导致大数字逐渐往右端移动、小数字逐渐往左端移动，最后一定能完成排序。

读者可以想想看：交换任意两个数字的排序法，成立吗？

顺带一提，排序过程反向操作，可以得到一个结论：排序过的阵列，经由两两相邻交换，一定可以得到各种排列方式。

范例：荷兰国旗问题（Dutch National Flag Problem）

http://www.iis.sinica.edu.tw/~scm/ncs/2010/10/dutch-national-flag-problem/

http://www.iis.sinica.edu.tw/~scm/ncs/2010/10/dutch-national-flag-problem-2/

http://www.iis.sinica.edu.tw/~scm/ncs/2010/10/dutch-national-flag-problem-3/

范例：工作排程问题（Single Machine Scheduling, Minimize the Number of Tardy Jobs）（1||∑Ui）

有一位苦命上班族，要马上处理临时指派的 N 份工作。经验老到的他，马上就精准的估计出每份工作各要花掉多少时间，可是每份工作都有不同的完工期限，这造成有些工作可能会来不及完成。他做事专心，要求品质，一次只处理一份工作，一份一份接著做；来不及完成的工作，乾脆放弃不做。

请找出一种排程，让如期完成的工作最多（也就是让逾期完成的工作最少），顺便让总工时越短越好。

合理排程之相邻交换性质：

一个合理排程，其中某两个如期完成的工作 A 与 B，A 与 B 紧邻完成，A 早做 B 晚做，A 期限晚 B 期限早（或期限相同），则 A 与 B 对调位置之后，仍是一个合理排程。分析如下：

A 与 B 视作一体进行交换：排程裡的其他工作皆不受影响。
A 放到 B 的位置：A 的期限比 B 还晚，B 都能如期完成了，所以 A 也能如期完成。
B 放到 A 的位置：B 提早做，更能如期完成。

一个合理排程，不断地进行相邻交换，终会形成“工作依照期限排序”的合理排程！反之亦然！小心，不相邻则不可贸然交换。

因此，我们只需著眼于“工作依照期限排序”的合理排程。

UVa 10026 11389

填答案的原则是：所有工作依照期限排序，依序加入排程。一次加入一个工作，一旦发现逾期，立即从排程当中抽掉工时最长的工作。

已经加入 N 个工作，排程裡有 M 个工作。
排程裡的工作，是前 N 个工作的最佳解。也就是说：
α. 这 M 个工作，全部如期完成。
β. 前 N 个工作之中，如期完成的工作数量最多就是 M。
γ. 前 N 个工作之中，这 M 个工作总工时最短。

以数学归纳法证明之。假设 N 成立，当第 N+1 个工作加入排程，有两种情况。

一、没有发生逾期：

这 M 个工作，本来就是如期完成、工作数量最多、总工时最短的最佳选择。第 N+1 个工作加入之后，αβγ依然成立。

二、发生逾期，立即抽出工时最长的工作：

这 M 个工作，已经能如期完成。抽出工时最长的工作，补上工时稍短（或相等）的第 N+1 个工作，更能如期完成了。α成立。

这 M 个工作，总工时已经是最短了，还是无法添加第 N+1 个工作，不得已抽掉一个工作，工作数量已经尽量多了。β成立。

抽出工时最长的工作，总工时下降最多。γ成立。

UVa 10154 ICPC 3277 4850

范例：工作排程问题（2-Machine Flowshop Scheduling）（F2||Cmax）

两台机器，N 份工作，一台机器一次只能处理一个工作。每份工作必须先经过初号机处理一段时间，再经过贰号机处理一段时间，才算处理完毕。

请找出一种排程，迅速完成所有工作。

1. 建立两个空的 List，叫做 L1 和 L2。
2. 从 N 个工作、2N 个工时当中，不断挑出工时最短的工作。
   如果最短工时是初号机的工时，该工作加到 L1 前端。
   如果最短工时是贰号机的工时，该工作加到 L2 后端。
3. L1 L2，即是排程。

1. 建立两个空的 List，叫做 L1 和 L2。
2. 对每一个工作，若初号机工时小于贰号机工时，该工作加到 L1，反之则加到 L2。
3. L1 照初号机工时由小到大排序。
   L2 照贰号机工时由大到小排序。
4. L1 L2，即是排程。

Scaling Algorithm

古之欲明明德于天下者，先治其国。　　　　

　　　　　欲治其国者，先齐其家。　　　　

　　　　　欲齐其家者，先修其身。　　　　

　　　　　欲修其身者，先正其心。《礼记》

Fixed Parameter Algorithm

“固定参数演算法”。当问题太过困难，就增加限制，将部分变数改成常数。

范例：三维函数绘图

一、固定 X 值，计算 Y 值 Z 值；尝试各种 X 值。

二、固定 Y 值，计算 X 值 Z 值；尝试各种 Y 值。

三、固定 Z 值，计算 X 值 Y 值；尝试各种 Z 值。

Scaling Algorithm

“缩放演算法”。将数值拆解为不同数量级，每个数量级分别计算一次答案，并且累计每次计算成果。

范例：乘法

数量级从小到大：乘数拆解为不同数量级，先以个位数相乘一次，再以十位数相乘一次，……，再以最高位数相乘一次，累加起来，得到正确结果。

范例：基数排序法（Radix Sort）

数量级从小到大：所有数字先以个位数排序一次，再以十位数排序一次，……，再以最高位数排序一次，得到正确结果。

数量级从大到小：所有数字先以最高位数排序一次，再以前两高位数排序一次，……，再以全部位数排序一次，得到正确结果。

改善计数排序法的效率，不必建立一长串阵列。

范例：多重解析度匹配（Multiscale Matching）

从宏观到微观，从粗糙到细腻。短字串跳 N 格实施匹配。若足够相似，才跳 N/2 格实施匹配。……。若足够相似，才跳 1 格实施匹配。

改善匹配的效率，不必每次都比对一大串字元。

范例：Shell 排序法（Shell Sort）

从宏观到微观，从粗糙到细腻。跳 N 个数字为同一组，每组分别实施插入排序法。跳 N/2 个数字为同一组，各组分别实施插入排序法。……。跳 1 个数字为同一组，所有数字实施插入排序法。

改善插入排序法的效率，不必每次都挪动一大串数字。

External Memory Algorithm

士农工商四民者，国之石，民也。　　　　　　

不可使杂处，杂处则其言哤，其事乱。《管子》

Cache-oblivious Algorithm

储存容量大，存取时间长；储存容量小，存取时间短。鱼与熊掌不可兼得。自然而然形成阶层式架构：暂存器、快取、记忆体、硬碟，储存容量越来越大，存取时间越来越久。

需要计算的变数，储存在暂存器；不在暂存器，就找快取；不在快取，就找记忆体；不在记忆体，就找硬碟。

简中译作寄存器、缓存、内存、硬盘。

对中央处理器来说，最花时间的动作，不是运算，而是从记忆体读入资料到快取、从快取写出资料到记忆体。

每当变数不在快取，就从记忆体载入资料到快取，载入变数所在的那一个区块。区块大小等于通道容量，区块位置似乎固定不变。

“快取无视演算法”目的是减少载入次数。实际的通道容量、快取容量，端看硬体规格，无法预知。我们只能尽量集中变数，以减少载入次数。

“快取无视演算法”的名称由来是：考虑记忆体与快取，但是不知道通道容量、快取容量。以现代眼光来看，显然词不达意。

范例：阵列与串列

阵列在记忆体裡是连续的。串列在记忆体裡通常不是连续的。

枚举阵列元素，偶尔载入区块，不会重複载入，速度快。

枚举串列元素，经常载入区块，甚至重複载入，速度慢。

范例：二维阵列的总和

依序枚举二维阵列的所有元素，累计总和。

枚举横条元素，偶尔载入区块，不会重複载入，速度快。

枚举直条元素，经常载入区块，甚至重複载入，速度慢。

Parallel Algorithm（Under Construction!）

众心成城，众口铄金。《国语》

Parallel Algorithm

“循序 Sequential”就是逐一计算，“平行 Parallel”就是一齐计算，两者是相对概念。

“平行演算法”。当计算顺序无所谓时，就可以使用多个计算器一齐计算。优点是减少计算时间，缺点是增加硬体、增加电力。

详细架构是：一份记忆体，多个计算器。一份记忆体一齐传递资料给各个计算器，多个计算器一齐计算，多个计算器一齐传递资料给一份记忆体。

计算器又有两种类型：多个计算器只能一齐执行相同指令（例如 GPU），多个计算器可以分头执行不同指令（例如多核心处理器）。前者富含巧思，后者缺乏变化，所以我们只谈前者。

范例：複制字串

理论：各个字元分头複制，时间複杂度从 O(N) 变 O(1)。

实务：字串切成数段，分头複制。

因为作业系统建立执行绪需要大量时间与空间，所以平行计算不一定比循序计算好。程式员必须自行取捨。

范例：加总数字

理论：数字双双相加，时间複杂度从 O(N) 变 O(logN)。

实务：阵列切成数段，分头计算总和。最后累加各段总和。

Randomized Algorithm

有过物者必济，故受之以既济。《易传》

致中和，天地位焉，万物育焉。《礼记》

Randomized Algorithm

“随机化演算法”。随便的运算数值、计算顺序。难得糊涂。

范例：随机数字（Random Number）

随机数字又称乱数。乱七八糟、毫无章法、什麽都有可能。

如何制造乱数呢？没人知道！数学家尚未釐清“乱”是什麽。计算学家则创造了形形色色的算式，伪造乱数，聊胜于无。

简易算式：乘上一数、加上一数，递推下去。

C 程式语言的内建函式库，已经有乱数了。