演算法筆記 - Algorithm Analysis

Algorithm Analysis

演算法可以切開為兩個部分：演算法設計、演算法分析。

演算法設計：製造演算法。演算法設計目前已經有一些經典手法，例如Dynamic Programming、Greedy Method等等。

演算法分析：針對特定演算法，精確計量時間複雜度和空間複雜度。演算法分析會用到很多數學知識。下面這兩本書內容很詳細，我想應該不太需要再重複整理一遍。

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

https://prof.msoltys.com/?page_id=404

以下章節是隨興所至談天說地，參考看看就好。

時間複雜度

想要描述一個演算法執行速度有多快，直覺的方式是測量演算法計算時間。但是由於執行時間深受機器規格與實作方式影響，難以放諸四海皆準，因此學術上傾向於統計演算法步驟數目。

現在大家採用的方式是統計演算法步驟數目。但是由於每個步驟的執行時間都不一樣，加減較快、乘除較慢，因此這也是不那麼準確的方式。更何況，實際上的運作過程，是將程式碼編譯成機器碼，然後實施Instruction Pipeline。指令數量、演算法的步驟數目，兩者根本沒有絕對關係。

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

時間複雜度標記法

時間複雜度的標記法，是幾十年前的數學家發明的方式：大寫的英文字母O函數，代表演算法執行步驟數目上限；大寫的希臘字母Ω函數，代表下限；大寫的希臘字母Θ函數，代表同時滿足上限與下限（不多不少剛剛好）。

這些上限下限，都是假設演算法輸入長度N足夠大、甚至無限大。又由於N足夠大，所以我們只需比較函數的最高次方項。另外我們省略了最高次方項的係數。

因為省略了很多東西，所以時間複雜度往往無法正確反映演算法的快慢。例如N=100的情況下，有可能O(N³)的演算法表現的比O(N²)好。例如兩個同為O(N)的演算法可能不一樣快，N大時甲快、N小時乙快。

時間複雜度標記法，也完全忽略了I/O處理和記憶體管理的問題。要是資料結構複雜一點、龐大一點，讀取資料就會變慢。

時間複雜度標記法，也完全忽略了程式語言特性和平台特性。同一個演算法，用C寫執行較快，用Java、Python寫執行較慢。因為後者的記憶體管理機制更加複雜，而且牽扯到系統運作架構。

時間複雜度標記法再怎麼不可靠，也比不上實作的不可靠。同一個演算法，不同人寫出來的程式碼，執行效率都不一樣，相差十倍都有可能。

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

輸入資料

輸入資料常常影響時間複雜度。舉例來說，當輸入資料已經排序完畢，此時實施排序演算法，只需檢查一遍輸入資料，即可發現根本無須排序，直接結束演算法，時間複雜度O(N)！

當輸入資料很整齊，那我們可以得到最佳或最壞的時間複雜度是多少；當輸入資料很亂，那我們可以得到平均的時間複雜度是多少。例如Quicksort，最佳O(N)，平均O(NlogN)，最差O(N²)。

另外還想強調一件事：最佳、平均、最壞跟Ω、Θ、O沒有關係，不知道為什麼很多人覺得它們是對應的。

Smoothed Analysis則是分析輸入資料有多少機率是整齊的、多少機率是亂的。

計算步驟

演算法的步驟數目不是固定的時候，可以使用Probabilistic Analysis和Amortized Analysis和Competitive Analysis。

當今電腦計算能力的極限

也許各位已經聽聞過當今七大數學難題之一「P = NP問題」。目前的電腦運算能力其實差強人意，絕大多數的問題都沒辦法快速地求解。就算找來大量電腦實施平行計算，依然沒辦法快速地求解。

然而，現代人類對於電腦有著神祇般的依賴，各種日常生活問題都祈望電腦能夠幫上忙。於是近似演算法出現了，用來求得一個馬馬虎虎差不多的答案。

計算方式

現今流行的計算機，是由邏輯電路組成，使用AND與OR，兜出加減乘除四則運算，運算能力差強人意。遇到NP問題，就得耗費大量計算時間，無法迅速求得答案。

除了邏輯電路以外，其實還有其他方式，諸如Quantum Computing、Optical Computing、DNA Computing。這些計算方式，運算能力極強，計算時間極短。之所以不流行，是因為計算難以控制、機器難以量產。

一旦新的計算方式開始流行，我們現在習慣使用的時間複雜度分析方式，只能作古了。

NP-complete

示意圖

http://courses.csail.mit.edu/6.892/spring19/lectures/

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-complete之間的問題

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

為什麼學校老師要教NP-complete？

台灣的演算法課程，都是直接抄舊書，特別強調NP-complete，特別強調問題之間的轉換。不過職場上幾乎不會用到這些知識。學術上要解決P = NP問題，也不會用到這些知識。

現在比較新的教學資料，都是直接介紹多項式時間和指數時間的差異，而不是去介紹P、NP、NP-complete、NP-hard到底誰包含誰。

Weak NP-complete

Pseudo-polynomial Time

即便是NP-complete問題，當每個數字的數值很小，還是可能擁有快速的演算法。

「一堆整數，從中挑出一些，總和為0」是NP-complete問題。

總共N個數字，窮舉2ᴺ種數字組合方式，一一計算總和，判斷是不是零，那麼時間複雜度是O(2ᴺN)。再考慮數值大小為K位數，那麼時間複雜度是O(2ᴺNK)。

然而，當數字們的數值R很小，利用Dynamic Programming，表格大小為RN格，將各種組合方式記載於表格。每讀取一個數字，就更新整個表格，那麼時間複雜度是O(RNN)。再考慮數值大小為K位數，那麼時間複雜度是O(RNNK)。

R其實是2ᴷ，O(RNNK)其實是O(2ᴷNNK)，只不過K很小。外觀是多項式時間，實際執行也是多項式時間，本質卻是指數時間，因此稱作「偽多項式時間」。

Weak NP-complete問題、Strong NP-complete問題

NP-complete問題，可以達到偽多項式時間者，稱做Weak NP-complete問題；反之稱作Strong NP-complete問題。

「一堆整數，從中挑出一些，總和為0」是Weak NP-complete問題。
「判斷一張圖是否存在Hamilton Path」是Strong NP-complete問題。

NP-complete、NP-hard並不是好的分類方式，導致事情很複雜。我真的不想介紹NP-complete。但是教科書都這樣教，我也只好配合一下。

P versus NP

P = NP ?

這是計算機科學的一個懸案。大意是說：到底NP問題能不能用多項式時間演算法解決呢？如果可以的話，那麼NP問題就都變成了P問題了。

有一個解決這個懸案的方向是：嘗試發明一個多項式時間演算法，解決某一個NP-complete問題（所有NP問題當中最複雜的問題）。接著我們可以將此NP-complete問題進行特例化得到所有NP問題，如此一來，所有NP問題都可以用此多項式時間演算法算出答案了。

很多人聲稱自己已經成功證明了，但是至今還沒有一個讓所有人都信服的證明：

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

一個演算法的時間複雜度下限

演算法教科書，都會提及時間複雜度上限O函數，但是鮮少提及時間複雜度下限Ω函數。比方說最短路徑問題，Dijkstra演算法是O(N²)，Floyd-Warshall演算法有三個迴圈是O(N³)，大家肯定耳熟能詳。但是Dijkstra演算法的時間複雜度下限是多少呢？其實也是Ω(N²)。由於上下限一樣，可以進一步寫成Θ(N²)。

Dijkstra演算法是確定性演算法，每個步驟都是確定的、固定的，所以時間複雜度上限和下限是一樣的，沒有特地討論的必要。

一個問題的時間複雜度下限

最短路徑問題，Dijkstra演算法是O(N²)，再使用priority queue則降低至O(ElogE)，有各式各樣的手段可以降低時間複雜度上限。但是最短路徑問題的時間複雜度下限至少是多少呢？演算法教科書沒講！原因是下限非常難以證明。

想要證明上限，只需想出一個時間複雜度更低（更快）的演算法，便得到了新的上限、更低一點的上限。想要證明下限，卻必須窮舉所有可能的演算法，證明沒有任何時間複雜度更低（更快）的演算法，才能得到新的下限、更高一點的下限。「列舉一個」與「窮舉全部」的差別，這就是困難所在之處。

目前只有少數幾個問題，內容簡單、具有嚴格限制的問題，可以明確證明下限：

一個經典的例子是「兩兩比較的排序演算法」，最少必須比較NlogN次，時間複雜度下限是Ω(NlogN)。證明方式是用樹狀圖展開所有可能性，樹的末端節點共N!個，樹的高度至多是logN! ≤ logNᴺ = NlogN。

然而，排序演算法還有counting sort、hashing這些可能性，不一定只能兩兩比較。限制成兩兩比較，非常不切實際。

另一個經典的例子是「求出一群點的凸包」，化成兩兩比較的排序問題，得到時間複雜度下限是Ω(NlogN)。

然而，如果解除了兩兩比較的限制，便有時間複雜度更低的演算法。設定這種限制，非常不切實際。

例子少得可憐。現況就是如此。

P = NP問題的困難之處，在於證明時間複雜度下限。必須證明NP問題的時間複雜度下限，到底是和P一樣是多項式時間、或者是和NP-complete一樣是指數時間。超級難的！

另一種策略是改為證明NP問題的時間複雜度上限。只要找到任何一個多項式時間演算法解決任何一個NP-complete問題，就能確確實實的降低所有NP問題的上限。不過目前也沒有人找到這樣一個演算法。

Complexity Class

https://complexityzoo.uwaterloo.ca

複雜度分類方式還滿多的。大家一直搞不定P = NP問題，於是大家不停深入鑽研細節，於是大家順手發明了一大堆分類。一般人不需要知道這些小細節，然而你現在還是見到了。

PTIME / PSPACE / EXPTIME / EXPSPACE  時間用量、空間用量
NC⁰ / AC⁰ / ACC⁰                     邏輯閘用量

P     判定問題
#P    計數問題
PP    機率判定問題

Approximation Algorithm

APX   有多項式時間演算法
      近似到 MINOPT⋅n 或者 MAXOPT⋅n 對於一個n

PTAS  有偽多項式時間演算法 (n的多項式，ε視作定值)
      近似到 MINOPT⋅(1+ε) 或者 MAXOPT⋅(1-ε) 對於所有ε

FPTAS 有多項式時間演算法 (1/ε和n兩種變數構成的多項式)
      近似到 MINOPT⋅(1+ε) 或者 MAXOPT⋅(1-ε) 對於所有ε

Randomized Algorithm

BPP   有多項式時間演算法
      出錯機率不超過1/2，正確機率至少1/2。
      執行 k 次，投票表決，讓出錯機率不超過 (1/2)ᵏ

RP    有多項式時間演算法
      當答案為Yes，有1/2機率出錯。
      當答案為No，絕對不會出錯。
      執行 k 次，投票表決，讓出錯機率降為 (1/2)ᵏ

ZPP   有多項式時間演算法
      要嘛回答正確答案，要嘛不知道答案，機率各1/2。

以隨機的運算數值、計算順序，取代不明的、糟糕的輸入數值、輸入順序。

一、不會影響答案。

二、避免偏頗答案。

隨機演算法必須運用機率來分析時間複雜度。一種計算順序，對應一個時間複雜度；考慮每一種計算順序的出現機率，求得時間複雜度的期望值。

一、不清楚輸入資料的分布情況，無從分析average case的時間複雜度──此時可以用隨機的計算順序，將時間複雜度的期望值，姑且當作是average case的時間複雜度。

二、十分清楚輸入資料的分布情況，而且輸入資料接近worst case──此時可以用隨機的計算順序破壞worst case，有很大機率能趨吉避凶，減少計算時間；但是也有一定機率會弄巧成拙，增加計算時間。

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

「精確演算法」是計算結果絕對正確的演算法。

「近似演算法」是計算結果擁有誤差的演算法。

有許多問題無法快速計算正確答案。為了追求速度，就會設計「近似演算法」。

Open Problem

「懸案」。目前還沒有人知道正確答案的問題。

Open Problem Garden
The Open Problems Project
10000个科学难题·数学卷
The Princeton Companion to Mathematics、普林斯頓數學指南

Intractable Problem

「難題」。難以設計快速的演算法。實務上的解法有：

一、數學規劃。請參考「Integer Programming」。
二、狀態空間搜尋。請參考「State」。
三、人工神經網路。請參考「Neural Network」。

以下做了簡單分類。注意到這不是公認的分類方式。

[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點，連接所有地點，成本盡量小。

[Routing] 規劃最佳路線。
Hamilton Circuit：拜訪所有景點的最短路線。
Vehicle Routing Problem：從起點出發多次，拜訪所有景點的最短路線。
Chess Problem：給定棋盤盤面，找到贏棋下法。

[Scheduling] 工廠進行生產製造、規劃最佳流程。
Open Shop Scheduling：每個工作在每一台機器都要做一次，隨便你用什麼順序做。
Job Shop Scheduling：每個工作已經規定好執行機器的順序。
Flow Shop Scheduling：每個工作所規定的執行機器順序都完全一樣。
Graph Coloring：地圖相鄰區塊填入不同顏色，顏色種類盡量少。
http://www.informatik.uni-osnabrueck.de/knust/class/