演算法複雜度 | EntangleTech 量子教育平台

# 演算法複雜度這節會是我們在進入量子計算前，介紹最後一個與電腦有關的重要觀念：演算法複雜度。透過演算法複雜度分析，我們可以判斷哪些問題是經典電腦不擅長而量子電腦擅長，並且量子電腦在某些情況下能比經典電腦快多少。 ## 何謂演算法在進入主題前，讓我們先簡單解釋何謂演算法。簡單來說，演算法就是解決問題的方法，這方法可以用文字、符號、程式碼或邏輯電路來描述。

在美劇《宅男行不行》第二季第 13 集，主角設計了如何交朋友的演算法

針對同一個問題，可以有很多種解決方法，那要如何評斷哪個方法比較好？這時候就需要「演算法複雜度分析」，這正是本節的主題。 ## 演算法複雜度分析面對同一個問題，A 和 B 各自用程式寫了一套演算法來解決這問題，身為主管的你該如何判斷誰的方法更好？你可能會看誰的方法所需的時間比較少，這就是時間複雜度（time complexity），或是你看誰的方法所需的硬體資源比較少，這就是空間複雜度（space complexity），本節我們將著重在前者的介紹，即時間複雜度。架設 A 的程式僅需要 3 秒解決問題，而 B 寫的程式需要 10 秒。我們能單純用秒數來評斷 A 的方法比 B 好嗎？顯然不行，即便是同個演算法，其執行時間也會因為每個人的環境、硬體設備等而有所差異，用「秒」來評估演算法好壞有失客觀性。為了客觀地評估演算法，數學家提出 Big O notation。 ## Big O notation Big O 用來表示當輸入數量 $n$ 非常大時，演算法所需的時間（實際上是步驟數）與輸入數量 $n$ 的關係，這就是 Big O 的概念。假設要從通訊錄裡找到某個人的電話號碼，經典電腦需要從第一筆資料開始找起，直到找到辣個人為止。在最壞的情況下，可能需要翻遍整本通訊錄。如果通訊錄有 20 筆資料，在最壞情況下電腦需要檢查 20 次，有 $n$ 筆資料就要檢查 $n$ 次。因此，經典電腦演算法的複雜度記做 $O(n)$。

經典電腦搜尋資料庫的流程圖

量子電腦因為疊加態的特性，可以一次搜尋所有的資料。不管 $n$ 多大，量子電腦都僅需檢查一次，因此量子電腦的複雜度記做 $O(1)$。

量子電腦搜尋資料庫的流程圖

這裡量子電腦的例子是比喻

當 $n$ 越來越大時，$O(n)$ 與 $O(1)$ 兩個算法的差異就越明顯。

常見複雜度類型

因為 Big O 是討論當 $n$ 非常非常大的狀況。如果你評估這演算法所需步驟數與輸入數量的關係是 $4n^2-2n+3$，當 $n$ 來到 $500$ 時，後面 $-2n+2$ 基本上沒什麼影響。與 $O(n^3)$ 相比，$n^2$ 的係數 $4$ 帶來的影響也很小，所以會直接記做 $O(n^2)$ ## 計算複雜性如果複雜度能用 $O(n^k)$（k 為任意數）描述，這種稱作多項式時間（polynimial time），統稱為 $P$，這類問題經典電腦都能輕易解決。

多項式與非多項式時間

量子電腦能在多項式時間內解決的問題稱作 BQP（Bounded-error Quantum Polynomial time）。目前已知 BQP 包含 P 問題，但有沒有包含 NP 問題仍不清楚，有沒有問題是屬於 NP 但不是 BQP 也是一個重要的研究議題。

在入門系列文章中出現的計算複雜性，目前很確定 BQP 包含 P，但 BQP 的邊界在哪仍不確定（圖中的 PSPACE 是空間複雜度，這邊就不多做介紹）

如果某問題的複雜度可用 $O(2^k)$ 描述，則稱作 non-deterministic polynomial time（NP），這類問題難以用電腦解決，但可以在多項式時間內驗證答案對不對，著名的旅行商問題就屬於此類。

計算科學中的大難題，P=NP?如果這等式成立，將意味所有目前已知難以用電腦解決的 NP 問題都能在多項式時間內解決，這將會是巨大的突破。

如果某問題的複雜度是 $O(2^{n^k})$，這問題就歸類於 EXPTIME，象棋與圍棋就屬於這類問題。 ## 結語了解演算法複雜度是進一步學習量子計算的基礎。透過這些知識，我們可以更好地理解量子電腦在某些問題上的優勢，以及經典電腦在處理特定問題時的限制。接下來，我們將進入量子計算主題，從最簡單的 qubit 開始，並逐步深入這個令人興奮的領域。