計算問題（computational problem）是一個能藉由做足夠計算來回答的問題，例如「2017 是質數嗎？」或「incomprehensibilities 裡有幾個字母 i？」

計算困難性（computational hardness）則是這樣一種性質：不存在能在合理時間內執行完畢的演算法。這類問題也稱為難解問題（intractable problems），實務上往往不可能解開。

令人意外的是，計算困難性與所用的運算裝置型態無關——不論是通用 CPU、積體電路，還是機械式圖靈機。

計算複雜度理論最早的發現之一就是：所有運算模型都是等價的。若一個問題能在某個裝置上有效率地解決，就能藉由把演算法移植到另一個裝置的語言，在任何其他裝置上有效率地解決。

（量子電腦是個例外，但它們還不存在。）

因此討論計算困難性時，我們不必指定底層的運算裝置或硬體，只談演算法就好。

衡量執行時間#

多數開發者都熟悉計算複雜度——一個演算法所執行的運算次數，作為其輸入大小的函式。大小以位元數或輸入的元素數量計算。

以下面這個在 n 個元素的陣列中搜尋值 x 並回傳其索引位置的演算法為例：

search(x, array, n):
    for i from 1 to n {
        if (array[i] == x) {
            return i;
        }
    }
    return 0;
}

複雜度就是 for 迴圈的迭代次數：

陣列大 10 倍，演算法就慢 10 倍。複雜度因此與 n 成正比，也就是對 n 呈線性。

從線性到指數#

線性複雜度被視為快，與對 n 呈指數的複雜度相對。處理較大的輸入值雖然較慢，但對多數實際用途而言差別頂多幾秒鐘。

但許多有用的演算法比這慢，複雜度高於線性。教科書級的例子是排序演算法：給定 n 個隨機順序的值，平均需要 n × log n 次基本運算來排序，這有時稱為線性對數複雜度（linearithmic）。由於 n × log n 成長得比 n 快，排序速度變慢的幅度會超過 n 的比例——但這類演算法仍屬於實際可計算的範疇。

再往上走就會撞到天花板。以密碼分析最簡單的例子——暴力搜尋秘密金鑰——為例：給定明文 P 與密文 C = E(K, P)，還原一把 n 位元對稱金鑰至多需要 2^n 次嘗試，因為有 2^n 把可能金鑰。

這是指數成長複雜度的例子。

對複雜度理論家而言，指數複雜度意味著這個問題實際上不可能解決——隨著 n 增長，所需的力氣會極快地變得不可行。

兩個常見疑問#

這個不一致在比較兩個複雜度非常接近的演算法時會有差別，但多數時候無關緊要——因為運算的次數比單次運算的成本影響更大。

複雜度分析談的是「作為輸入大小之函式」的理論困難性，它不在乎在你電腦上實際要花幾個 CPU 週期。

大 O 記法#

你常會看到用 O() 記法（大 O）表達複雜度。例如 O(n³) 表示複雜度成長不快於 n³，忽略潛在的常數因子——O() 標示的是演算法複雜度的上界。

例如「看整數的最低位元（LSB），為零就回傳偶數、否則回傳奇數」這個判斷奇偶的演算法，無論整數多長都做同樣的事、花同樣的成本。

三種複雜度的成長對照：

• O(n)（線性）：解法可行。
• O(n²)（二次）：介於兩者之間。
• O(2ⁿ)（指數）：問題實際上不可能解決。

多項式時間 vs. 超多項式時間#

上一節的 O(n²) 是更廣泛的多項式複雜度 O(n^k) 的特例，其中 k 是某個固定的數（如 3、2.373、7/10 或 17 的平方根）。

當一個演算法以多項式時間（簡稱 polytime）執行，即使輸入很大，它也會在還算合理的時間內完成。這就是為什麼對複雜度理論家與密碼學家而言，多項式時間就等於「有效率」。

相對地，以超多項式時間（superpolynomial time）執行的演算法——也就是 O(f(n)) 而 f(n) 成長快於任何多項式——被視為不實用。

這裡說「超多項式」而不只是「指數」，是因為在多項式與眾所周知的指數複雜度 O(2ⁿ) 之間還有其他複雜度，例如 O(n^log(n))。

成長速度：2ⁿ > n^log(n) > n²。

指數複雜度 O(2ⁿ) 還不是最糟的。有些複雜度成長得更快，例如 O(nⁿ) 或指數階乘 O(n^f(n−1))（其中 f(x) = x^f(x−1)）。實務上你永遠不會遇到複雜度荒謬到這種地步的演算法。

多項式時間的但書#

O(n²) 或 O(n³) 也許有效率，但 O(n^99999999999) 顯然不是。換句話說，只有在指數不太大的時候，多項式時間才算快。

所幸所有被找到用來解決實際問題的多項式時間演算法，指數都很小：

• 相乘兩個 n 位元整數：O(n^1.465)
• 相乘兩個 n × n 矩陣：O(n^2.373)
• 2002 年判定質數的突破性多項式演算法一開始是 O(n^12)，後來改進到 O(n^6)

多項式時間或許不是「演算法的實用時間」的完美定義，但它是我們手上最好的定義。

延伸來說，無法被多項式時間演算法解決的問題就被視為不實用，或「困難」。例如對直截了當的金鑰搜尋而言，除非該密碼被以某種方式攻破，否則沒有辦法勝過 O(2ⁿ) 的複雜度。

我們確知（只要密碼安全）無法勝過暴力金鑰搜尋的 O(2ⁿ)，但我們不總是知道解決一個問題最快的方法是什麼。複雜度理論研究有很大一部分，就是在證明「解決某給定問題之演算法」其執行時間的複雜度界限。