Algorithm PUBLISHED 2025年11月28日 UPDATED 2025年11月28日

認識演算法：啟程

在日常生活中，我們可能常聽到以下對話：

「YouTube 的演算法不知道為什麼推薦了我這支影片。」

「演算法為什麼要給我看這個廣告?」

演算法在今天早已成為所有一般大眾經常聽到的詞彙。

但是，到底什麼是演算法?

演算法和其存在的重要性

精簡定義上，演算法是一種明確定義的計算程序，它接收一個或一組值作為輸入，並在有限的時間內產生一個或一組值作為輸出。換句話說，演算法是將輸入轉換為輸出的一系列計算步驟。你也可以將它視為解決一個明確計算問題的工具。

演算法有極大的應用廣度，並且是現代電腦技術的基石。在應用層面上，包含人類基因組計畫、網際網路搜尋引擎、電子商務加密、工業製造資源分配等，這些應用的背後都有演算法在運作，是解決各類實際問題的關鍵。在電腦技術上，無論是硬體晶片設計、圖形使用者介面(GUI)、網路路由，還是程式語言的編譯器，這些電腦技術的背後也都有演算法在運作；另外，近年熱門的機器學習，它的本質也是一系列演算法的集合。

大部分的人可能很難想像，演算法作為一門技術，它的重要性其實完全不亞於硬體。會這樣說的原因是因為經過科學家的實驗，演算法的效率優勢，遠比硬體的性能差距更為顯著，尤其是在處理大規模問題時。

演算法效率分析

在簡單了解了演算法是什麼以及它存在的重要性後，接下來有一個很重要的問題是：我們要如何有系統的評估一個演算法的效率，並將它與其他演算法進行有意義的比較?

首先，要評估一個演算法的效率，我們必須先想辦法有一個公平的基準，因此這裡要介紹一個抽象的計算模型叫做 RAM model。

RAM model 的全名是 Random-Access Machine model（隨機存取機器模型），它是一個在分析演算法效率時所使用的抽象、理想化的電腦模型。

我們可以把它想像成一台通用型的單處理器電腦，它運作時有以下幾個關鍵的簡化假設：

循序執行(Sequential Execution)：所有指令都是一條接著一條依序執行的，不存在同時發生的並行操作。
等價的時間成本(Uniform Cost)：模型假設每條基本指令（例如：加、減、乘、除等算術運算，或載入、儲存等資料操作）花費的時間都是一個固定的常數時間。

這個模型的主要目的是提供一個統一的標準，讓我們可以專注在演算法本身步驟的效率，而不用去煩惱特定硬體、程式語言或作業系統所帶來的差異。儘管它忽略了真實電腦中的快取(cache)或虛擬記憶體等複雜機制，但它對於預測和比較演算法的效率通常已經非常有效。

再來，我們需要知道的是，在演算法分析中，我們通常最關心最差情況分析(Worst-case Analysis)，因為它為演算法的執行時間提供了一個可靠的上限保證，並且在許多實際應用中，最差情況或與其相近的「平均情況」其實相當常見。

以上兩點說明我們已經為評估一個演算法的效率建立了一個效能分析的框架，接著我們要引入讓我們可以有效分析演算法效率的另一個重要概念：成長階數(Order of Growth)。

計算一個演算法確切的執行時間表達式通常過於複雜且不必要，因為當輸入規模 n 變得足夠大時，執行時間主要由增長最快的項——我們稱為成長階數——決定，而常數倍數和低階項的影響則可以忽略不計。為了能夠簡潔的表達這個概念，我們會使用一套標準化的數學工具——漸進符號(Asymptotic Notation)——來表達這種只關注規模增長的分析演算法效率方式，也就是分析演算法的漸進效率(Asymptotic Efficiency)。

漸進效率會研究當輸入規模趨近於無限大時，演算法的執行時間如何隨輸入規模增長的情況。這是一種關注「極限」下效率表現的分析方式。

我們有以下五種的漸進符號可以使用：

$\pmb{O}$ -notation (大O符號)
- 定義：提供一個函數的漸進上界(asymptotic upper bound)。如果一個函數 $f(n)$ 是 $O(g(n))$ ，意味著當 $n$ 足夠大時， $f(n)$ 的增長速度不會快於 $g(n)$ 的常數倍。
- 直觀理解：為演算法的執行時間提供一個「最壞情況」的保證，表示執行時間的增長不會超過某個界限。
$\pmb{\Omega}$ -notation (大Omega符號)
- 定義：提供一個函數的漸進下界(asymptotic lower bound)。如果一個函數 $f(n)$ 是 $\Omega(g(n))$ ，意味著當 $n$ 足夠大時， $f(n)$ 的增長速度至少和 $g(n)$ 的常數倍一樣快。
- 直觀理解：為演算法的執行時間提供一個「最好情況」的保證，表示執行時間的增長不會低於某個界限。
$\pmb{\Theta}$ -notation (大Theta符號)
- 定義：提供一個函數的漸進緊確界(asymptotically tight bound)。如果一個函數 $f(n)$ 是 $\Theta(g(n))$ ，意味著它同時是 $O(g(n))$ 和 $\Omega(g(n))$ 。也就是說，當 $n$ 足夠大時， $f(n)$ 的增長速度和 $g(n)$ 的增長速度在常數因子範圍內是相同的。
- 直觀理解：最精確地描述了演算法執行時間的增長率。
$o$ -notation (小o符號)
- 定義：提供一個非漸進緊確的漸進上界(upper bound that is not asymptotically tight)。如果 $f(n) = o(g(n))$ ，表示 $f(n)$ 的增長速度遠慢於 $g(n)$ 。
- 與大O的區別： $O$ 允許增長率相同（如 $2n^2 = O(n^2)$ ），而 $o$ 要求增長率必須嚴格地更慢（如 $2n = o(n^2)$ ，但 $2n^2 \neq o(n^2)$ ）。
$\pmb{\omega}$ -notation (小omega符號)
- 定義：提供一個非漸進緊確的漸進下界(lower bound that is not asymptotically tight)。如果 $f(n) = \omega(g(n))$ ，表示 $f(n)$ 的增長速度遠快於 $g(n)$ 。
- 與大Omega的區別： $\Omega$ 允許增長率相同，而 $\omega$ 要求增長率必須嚴格地更快。

演算法設計策略

除了用好的方式評估一個演算法的效率這件事情很重要以外，再往更源頭看，有一套好的演算法設計策略也很重要。

所以接下來的問題是：我們要如何更好的設計演算法?

許多有用的演算法在結構上是遞迴的(recursive)：為了解決給定的問題，它們遞迴——也就是呼叫自己——一次或多次來處理與原問題相似但大小較小的子問題。這些演算法通常遵循分治法(Divide-and-Conquer)，它們將問題分解成幾個與原問題相似但大小較小的子問題，遞迴解決這些子問題，然後將這些解決方案組合成原問題的解決方案。

在分治法中，如果問題規模夠小——也就是基本情況——我們就直接解決它，而不進行遞迴。否則——遞迴情況——我們要執行三個特徵步驟：

分割(Divide)： 將問題劃分為一個或多個較小的相同問題的子問題。
征服(Conquer)： 透過遞迴解決這些子問題來征服它們。
合併(Combine)： 將子問題的解決方案合併，形成原問題的解決方案。

使用分治法是其中一個好的演算法設計策略，還有另一個可以幫助我們更好的設計演算法的策略是使用資料結構。

資料結構是一種儲存和組織資料的方式，目的是為了讓資料的存取和修改更加方便。

資料結構有很多類型，為特定問題選擇合適的資料結構是演算法設計中的重要一環。

演算法的難題

現在我們已經初步了解如何好的設計演算法和評估它的效率的方式了，最後我們也來談談現今演算法的難題。

關於演算法的難題，現今存在一類被稱為NP完備(NP-complete) 的問題，至今無人能找到有效率的解法。原因有三：

不確定性：雖然目前找不到高效解法，但也沒人能證明這種解法「絕對不存在」。
連動性：所有NP完備問題構成一個「命運共同體」。只要其中任何一個問題被找到高效解法，那麼所有NP完備問題都能迎刃而解。
相似性：它們往往與某些已知存在高效解法的問題極為相似，問題描述上的微小差異就可能導致它的難度從「容易」驟升至「困難」。

了解NP完備問題的現實意義在於：當我們遇到的問題被證明是NP完備時，就不該再浪費時間去尋找完美的最佳解。此時，更務實的策略是轉而開發「近似演算法」(Approximation Algorithm)，這種演算法雖然無法保證找到最佳解，但能在合理的時間內給出一個足夠好的答案。

參考資料

Introduction to Algorithms, fourth edition

附錄

本文為系列文章，目前寫了五篇: