簡介 -- 以排序為例

演算法是什麼? 「有規律地愚公移山」, 而且在乎完成工作所需要花費的時間與空間。

以排序為例: 有 n 張考卷, 希望由最低分排到最高分。

Selection Sort

最簡單的排序演算法之一: selection sort (選擇排序): 將 n 張考卷中最低分的那一個調到最前面, 再將剩下 (n-1) 張考卷中最低分的那一個調到第二個位置, 再將剩下 (n-2) 張考卷中最低分的那一個 ...

Selection sort 外層迴圈的 loop invariant: 第 k 步做完時, 所有考卷當中最低分的 k 張已就定位。

Mergesort

最簡單的 "高效率" 排序演算法: mergesort: 委請兩位朋友分別排序 (他們怎麼排是他們家的事, 我不操心), 回收他們的成果之後, 我只需要負責合併。 合併的工作很簡單: 只需要盯著兩疊考卷最上面這張看, 取走低分那張即可, 從來不需要翻下面的考卷。 (to do: 更多細節)

當然, 這兩位朋友也會依樣畫葫蘆 ...

從軟體執行的角度來看, 實際上是同一個副程式, 出現很多個分身在執行。

同樣的任務, 那種解法比較有效率?

想比較不同解法的效率, 就要先弄清楚我們到底希望如何衡量 「某一個演算法的效率」? 我們的衡量方式應把握幾個原則:

  1. 馬馬虎虎, 能簡化就簡化, 八九不離十就可以了。 (當然, 差太多也不行)
  2. 簡化時, 寧可高估 (保守/悲觀地估計), 不可低估 (大膽/樂觀地估計)。
  3. 眼光放遠, 切記小時候胖不算胖。

最直接的想法是以 "執行秒數" 來衡量。 問題是: 不同的硬體執行速度也大不相同, 為了研究演算法的效率, 卻要牽扯到硬體, 未免太複雜了。 根據 「簡化原則」, 我們改 "基本動作" 執行的次數, 例如 "比較指令 28 次, 拷貝指令 21 次, ..." 這樣分析出來的結果與硬體無關, 必要時只需要配合不同硬體的 "指令執行時間對照表", 就可以算出整個演算法執行的時間。

麻煩的是: 指令執行的次數不是固定的。 輸入資料量大的時候 (10 萬張考卷), 我們數出來的答案, 當然與輸入資料量小的時候 (20 張考卷), 數出來的答案不一樣。 我們要的是一個對照表: 如果只有 1 筆資料要排序, 需要 ... 指令各 ... 個; 如果有 2 筆資料要排序, 需要 ... 指令各 ... 個; ...

考卷張數 1 2 3 4 5 ...
比較 0 1 3 6 10 ...
拷貝 0 3 6 9 12 ...
跳躍 ... ... ... ... ... ...
... ... ... ... ... ... ...

這樣寫還是嫌太麻煩了; 還好類似的問題世界上早有一群懶惰的高手 -- 數學家 -- 解決過。 用一個 函數 就可以表達出表格上面一整列的資訊。 若有 n 張考卷要用 selection sort 的方法排序, 則需要執行 n*(n-1)/2 個 "比較" 指令, 3*(n-1) 個 "拷貝" 指令, ... (最上面一列不算, 它是自變量.) 所以總共耗時 n*(n-1)/2 * tcmp + 3*(n-1)*tcpy + ... 其中 tcmp 代表執行一個 "比較" 指令所需要的時間, tcpy 代表執行一個 "拷貝" 指令所需要的時間, ... 等等。

符號還是太多了, 這些 tcmp, tcpy, ... 可否合併? 根據 「寧可高估原則」, 不妨看看這部機器最慢的指令要執行多久 (記做 t 好了), 那麼總執行時間大約是 (總之不會超過) (n*(n-1)/2 + 3*(n-1)) * t

反正不同的機器乘不同的 t, 而我們有興趣的是演算法, 又不是機器, 這個 t 還留著它幹嘛? 我們改用 0.5*n*n + 2.5*n - 3 來表示 selection sort 演算法的執行時間

根據 「眼光放遠原則」, 我們看看當 n 很大的時候, 跟 0.5*n*n 比起來, 2.5*n-3 不過是杯水車薪, 九牛一毛, 算什麼呢? 根據 「簡化原則」, 只留下 0.5*n*n 就好。 最後, 乾脆把 0.5 的帳算到機器頭上去 (剛才省略的 t), 我們說: selection sort 演算法的 time complexity 時間複雜度, 是 O(n^2)。 直覺解釋是: 以 selection sort 方式排序, 花費時間長短, 受資料量大小的影響程度 有平方的關係: 輸入資料量如果加倍, 則花費時間大約會變四倍; 輸入資料量如果變成十倍, 則花費時間大約會變一百倍。

這裡的 O, 有嚴格的數學定義 (見下章), 但是直覺的解釋更重要: 它像是一個垃圾桶, 把我們馬馬虎虎隨便亂算所造成的誤差全部都吃進去了, 我們才得以享受括弧內簡單的數學式。 用英文成語 "sweep it under the rug" 來說, 它就是那張藏污納垢的地毯。 當然它也並非大小通吃, 照單全收, 它有它的原則:

  1. 3 倍, 197.2 倍的差別都算不了什麼; n 倍就無法接受了。
  2. n 很小的時候它的包容力很強 (也就是說我們的算式如果在 n 很小的時候錯得非常離譜也沒有關係)