演算法思維入門

前言

如何有效率地解決問題？ 你可能遇過這樣的困惑：同一個問題，有人寫的程式跑幾秒就出結果，有人寫的跑幾分鐘還在轉。差別往往在於演算法。本章帶你理解演算法的核心思維方式。

這篇文章會帶你學什麼？

學完這章後，你將獲得：

問題拆解能力：面對複雜問題，能想到用分治、遞迴等策略拆解，而不是一上來就寫程式碼
效率判斷能力：用大 O 表示法判斷兩種解法哪個更高效，而不是憑感覺猜測
複雜度思維：寫程式碼前先估算資料規模和時間要求，選擇合適的演算法級別
後續學習基礎：為進階資料結構、分散式系統、機器學習打下基礎

章节	內容	核心概念
第 1 章	二分搜尋	分治思想、O(log n)
第 2 章	排序演算法	氣泡排序、快速排序、合併排序
第 3 章	複雜度分析	時間複雜度、空間複雜度

0. 全景圖：演算法是什麼？

想象你要在一本字典裡找一個單詞：

方法一：從第一頁開始，一頁一頁翻（線性搜尋）
方法二：根據首字母定位，再二分搜尋（二分搜尋）

兩種方法都能找到，但效率天差地別。演算法就是解決問題的方法。

Algorithmic Thinking: Ways to Solve ProblemsDifferent strategies fit different kinds of problems

Binary searchEliminate half each time, O(log n)

Search in a sorted array:

Time Complexity Quick Reference

O(1)ConstantBest, such as array access

O(log n)LogarithmicVery good, such as binary search

O(n)LinearCommon, such as traversal

O(n log n)LinearithmicAcceptable, such as quicksort

O(n²)QuadraticSlow, such as bubble sort

O(2ⁿ)ExponentialVery slow, such as brute-force recursion

Core idea:Algorithms are methods for solving problems. A good algorithm can improve efficiency by orders of magnitude. Understanding algorithmic thinking matters more than memorizing individual algorithms.

演算法的核心指標：

指標	含義	為什麼重要
時間複雜度	執行時間隨資料量增長的趨勢	預測大規模資料的效能
空間複雜度	記憶體佔用隨資料量增長的趨勢	評估記憶體消耗
正確性	是否總能得到正確結果	演算法的基本要求

逐行解讀這張表

時間複雜度：用大 O 表示法描述。O(n) 表示資料量翻倍，時間翻倍；O(n²) 表示資料量翻倍，時間變成 4 倍。

空間複雜度：同樣用大 O 表示法。有些演算法用空間換時間（如雜湊表），有些用時間換空間（如壓縮演算法）。

正確性：演算法必須對所有可能的輸入都能給出正確結果。邊界條件（空輸入、極大輸入）最容易出錯。

1. 二分搜尋：每次排除一半

1.1 二分搜尋的原理

二分搜尋如何運作？

前提：資料必須有序

過程：

找到中間元素
如果中間元素等於目標，找到了！
如果目標小於中間元素，在左半部分繼續
如果目標大於中間元素，在右半部分繼續
每次排除一半，直到找到或確定不存在

時間複雜度：O(log n)

生活類比：猜數字遊戲。我想一個 1-100 的數，你每次猜中間，我告訴你大了還是小了。最多猜 7 次就能猜中（因為 2⁷ = 128 > 100）。

動手試試看：下面這個演示展示了二分搜尋的運作原理，你可以選擇順序搜尋或二分搜尋來對比：

Search AlgorithmsHow to find a target in data

Linear search: check items one by one

Target number:

Time complexity: O(n)

Use case: unordered arrays

Performance Comparison

Data size	Linear search	Binary search
10	At most 10 steps	At most 4 steps
100	At most 100 steps	At most 7 steps
1000	At most 1000 steps	At most 10 steps
10000	At most 10000 steps	At most 14 steps

1.2 為什麼二分搜尋這麼快？

資料量	線性搜尋	二分搜尋
100	100 次	7 次
1,000	1,000 次	10 次
1,000,000	1,000,000 次	20 次
1,000,000,000	1,000,000,000 次	30 次

逐行解讀這張表

第一列（資料量）：要搜尋的資料有多少。可以看到資料量從 100 增長到 10 億（擴大了 1000 萬倍！）

第二列（線性搜尋）：最「笨」的方法，從第一個開始一個一個找。搜尋次數等於資料量，資料量越大，搜尋次數越多。

第三列（二分搜尋）：聰明的方法，每次排除一半。搜尋次數只和資料量的對數有關，即使 10 億資料也只需要 30 次！

對比結論：當資料量達到 100 萬時，線性搜尋需要 100 萬次，二分搜尋只需要 20 次——差距達 5 萬倍！

對數增長的威力

二分搜尋的時間複雜度是 O(log n)，這意味著：

10 億資料，最多搜尋 30 次
1 兆資料，最多搜尋 40 次

這就是對數增長的威力——資料量增加 1000 倍，搜尋次數只增加 10 次。

2. 排序：將無序變有序

2.1 常見排序演算法

演算法	時間複雜度	特點	適用場景
氣泡排序	O(n²)	簡單但慢	教學、小資料量
選擇排序	O(n²)	簡單但慢	小資料量
插入排序	O(n²)	對近乎有序的資料快	小資料量、近乎有序
快速排序	O(n log n)	實際最快	通用排序
合併排序	O(n log n)	穩定排序	需要穩定性的場景
堆積排序	O(n log n)	原地排序	記憶體受限場景

逐行解讀這張表

氣泡排序：最基礎的排序演算法，就像水底的氣泡往上冒一樣。簡單易懂，但速度最慢。適合學習排序思想，不適合實際使用。

選擇排序：每次選出最小的放到前面。也很簡單，但無論資料是否有序都要做同樣多的比較。

插入排序：像打撲克牌時整理手牌一樣。把每個元素插入到前面已經排好序的部分中。對近乎有序的資料效率很高。

快速排序：實際開發中最常用的排序。平均情況下最快，但最壞情況（資料已經有序）會退化到 O(n²)。

合併排序：採用「分而治之」的思想，總是 O(n log n)，但需要額外空間。適合需要穩定排序的場景。

堆積排序：利用堆積這種資料結構的排序，原地排序（不需要額外空間），但實際執行往往比快速排序慢。

2.2 為什麼快速排序「快」？

快速排序的原理

核心思想：分治法

選一個「基準」元素
把比基準小的放左邊，比基準大的放右邊
對左右兩部分遞迴排序
合併結果

為什麼快？

每次劃分後，基準元素就到了最終位置
平均情況下，每次劃分大約排除一半元素
時間複雜度 O(n log n)

生活類比：整理書架。先抽出一本書，把比它薄的放左邊，比它厚的放右邊。然後對左右兩堆分別重複這個過程。

動手試試看：下面這個演示展示了排序演算法的視覺化，你可以產生陣列，觀察氣泡排序和快速排序的過程對比：

Sorting AlgorithmsPut data into order

Choose a sorting algorithm

Select a sorting algorithm to start the demo

Time complexity:

Algorithm Comparison

Algorithm	Average time	Worst time	Space	Stable
Bubble sort	O(n²)	O(n²)	O(1)	✓
Quick sort	O(n log n)	O(n²)	O(log n)	✗
Merge sort	O(n log n)	O(n log n)	O(n)	✓
Insertion sort	O(n²)	O(n²)	O(1)	✓

3. 遞迴：自己呼叫自己

3.1 遞迴的本質

什麼是遞迴？

遞迴是函式呼叫自身的程式設計技巧。

兩個關鍵要素：

基本情況：什麼時候停止遞迴？
遞迴步驟：如何把問題分解成更小的子問題？

經典例子：階乘

function factorial(n) {
  if (n <= 1) return 1        // 基本情況
  return n * factorial(n - 1) // 遞迴步驟
}

生活類比：俄羅斯套娃。打開一個娃娃，裡面是更小的娃娃，直到最小的那個打不開為止。

3.2 遞迴 vs 迭代

特性	遞迴	迭代（迴圈）
程式碼簡潔度	通常更簡潔	可能更複雜
記憶體消耗	較高（呼叫堆疊）	較低
效能	稍慢（函式呼叫開銷）	更快
適用場景	樹遍歷、分治演算法	簡單重複任務

逐行解讀這張表

程式碼簡潔度：遞迴通常只需要幾行程式碼就能表達複雜的邏輯（如遍歷樹結構），而用迴圈可能需要更多的變數和巢狀。

記憶體消耗：遞迴會使用「呼叫堆疊」來儲存每一層的資訊，就像疊盤子一樣，每遞迴一層就多一個盤子。迴圈則不需要這種開銷。

效能：每次函式呼叫都有開銷（參數傳遞、堆疊操作等），所以遞迴通常比迴圈慢一些。

適用場景：遞迴擅長處理本身就是遞迴結構的問題（如檔案樹、DOM 樹）；迴圈擅長簡單的重複操作（如遍歷陣列）。

遞迴的陷阱

堆疊溢位：遞迴層次太深，呼叫堆疊空間耗盡。

解決方法：

改用迭代
使用尾遞迴最佳化（某些語言支援）
限制遞迴深度

動手試試看：下面這個演示展示了遞迴的呼叫過程，觀察函式如何自己呼叫自己：

Recursive Thinking: A Function Calls ItselfBreak a large problem into smaller problems of the same kind

🪆

Nested dolls

Open a large doll and there is a smaller doll inside
Open that one and there is an even smaller one, until the smallest case
That is recursion.

Recursive examples

Factorial: n! = n × (n-1)!

5! = 5 × 4!

↓

4! = 4 × 3!

↓

3! = 3 × 2!

↓

2! = 2 × 1!

↓

1! = 1 (base case)

↑ return 1

↑ return 2 × 1 = 2

↑ return 3 × 2 = 6

↑ return 4 × 6 = 24

↑ return 5 × 24 = 120

Three Elements of Recursion

Base case

When should recursion stop? There must be a termination condition.

Example: 1! = 1

Recursive call

How does the problem get smaller? Call the same function on a smaller case.

Example: turn n! into (n-1)!

Return result

How does the current problem use the result of the subproblem?

Example: the result of n × (n-1)!

✓ Pros

Concise code
Naturally expresses recursive structures
Good for tree and graph traversal

✗ Cons

May repeat work
Uses stack space
Can be harder to debug

4. 貪婪演算法：每步選最優

4.1 貪婪的思想

什麼是貪婪演算法？

貪婪演算法在每一步都選擇當前看起來最優的選擇，希望最終得到全域最佳解。

適用條件：

貪婪選擇性質：區域最佳能導致全域最佳
最佳子結構：問題的最佳解包含子問題的最佳解

經典例子：硬幣找零

目標：用最少的硬幣湊出指定金額
貪婪策略：每次選最大的硬幣
結果：67 元 = 50 + 10 + 5 + 1 + 1（5 枚）

生活類比：登山時，每次都選最陡的路往上走。雖然不一定能到最高峰，但通常能到不錯的位置。

4.2 貪婪的侷限性

貪婪不一定得到最佳解

反例：硬幣找零

如果硬幣面值是 [1, 3, 4]，要湊 6 元：

貪婪：4 + 1 + 1 = 3 枚
最佳：3 + 3 = 2 枚

貪婪演算法在這裡失敗了！

教訓：貪婪演算法簡單高效，但不總是能得到最佳解。使用前要證明問題滿足貪婪條件。

動手試試看：下面這個演示展示了貪婪演算法的實際效果，你可以嘗試不同的硬幣組合，觀察貪婪策略的表現：

Greedy Algorithms: Choose the Best Current MoveLocal optimum → global optimum?

A greedy algorithm chooses the best option available at each step
It hopes a series of local choices reaches a global optimum

Classic problems

Coin Change Problem

Change needed: 37

× 1 = 20

× 1 = 10

× 1 = 5

× 2 = 2

Needs 5 coins total

✓ Greedy strategy: choose the largest coin each time
✓ Works for currencies such as RMB and USD

Greedy vs Dynamic Programming

Feature	Greedy algorithm	Dynamic programming
Decision style	Choose the current best each step	Consider all possibilities and choose the best
Optimality	May not be globally optimal	Guarantees a global optimum
Time complexity	O(n) or O(n log n)	O(n²) or higher
Best fit	Local optimum → global optimum	Overlapping subproblems

✓ Pros

Simple to implement
Efficient
Low space complexity

✗ Cons

Does not always guarantee a global optimum
Limited applicability
Requires an optimality proof

5. 演算法設計範式

範式	思想	典型演算法	適用問題
分治	把問題分解成小問題	快速排序、合併排序	可分解的問題
貪婪	每步選最優	最小生成樹、霍夫曼編碼	有貪婪性質的問題
動態規劃	記錄子問題的解	背包問題、最短路徑	有重疊子問題
回溯	試錯，走不通就退回	八皇后、全排列	搜尋問題

逐行解讀這張表

分治：把大問題拆成小問題，分別解決後再合併。就像整理房間，先分成客廳、臥室、廚房分別打掃，最後整體整潔。

貪婪：每步都選當前最好的，不考慮長遠後果。像吃飯時先挑最喜歡吃的菜，可能不是最好的吃法，但速度快。

動態規劃：記住中間結果，避免重複計算。像記筆記，下次遇到同樣問題直接查答案，不用重新推導。

回溯：走不通就退回來重試。像走迷宮，此路不通就回到上一個路口嘗試別的路。

動手試試看：下面這個演示展示了不同演算法設計範式的特點和應用場景：

Algorithm Design ParadigmsCommon patterns for solving problems

Algorithm design paradigms are general strategies for solving problems. Learning them helps you find solution ideas quickly.

✂️

Divide and conquer

Divide, solve, combine

📊

Dynamic programming

Store results to avoid repetition

🎯

Greedy

Local optimum

🔙

Backtracking

Try and retreat

✂️Divide and conquer

Core idea

Split a large problem into smaller independent problems, solve them recursively, then combine the results.

Use cases

Array sortingMatrix multiplicationLarge integer arithmetic

Classic problems

📝

Merge sort

📝

Quick sort

📝

Binary search

📝

Strassen matrix multiplication

Time complexity

O(n log n)

Often much faster than brute force

Paradigm Comparison

Paradigm	Core strategy	Optimality	Use case
✂️ Divide and conquer	Split → recurse → combine	Guarantees optimum	Problems that split independently
📊 Dynamic programming	Store subproblem answers	Guarantees optimum	Overlapping subproblems
🎯 Greedy	Choose the best each time	Not always optimal	Local optimum → global optimum
🔙 Backtracking	Depth-first search	Guarantees optimum	Small search spaces that need enumeration

How to choose the right paradigm?

Analyze problem features

Are there overlapping subproblems? Is there optimal substructure?

Decide whether an optimum is required

Greedy is not always optimal; dynamic programming guarantees an optimum.

Consider input size

Backtracking fits small inputs, while divide and conquer fits larger inputs.

6. 總結：演算法是解決問題的藝術

讓我們用一個比喻總結各種演算法思想：

思想	比喻	核心要點
二分搜尋	猜數字	每次排除一半
排序	整理書架	建立秩序
遞迴	俄羅斯套娃	化大為小
貪婪	登山選路	區域最佳

核心啟示

演算法的本質是「效率」和「正確性」的平衡。

好的演算法能讓程式效率提升幾個數量級
但過度最佳化可能引入複雜性
先保證正確，再追求效率

理解演算法思維，比記住具體演算法更重要：

分治：把大問題分解成小問題
貪婪：每步選最優
動態規劃：記錄子問題的解
回溯：試錯，走不通就退回

演算法思維入門 ​

0. 全景圖：演算法是什麼？ ​

1. 二分搜尋：每次排除一半 ​

1.1 二分搜尋的原理 ​

1.2 為什麼二分搜尋這麼快？ ​

2. 排序：將無序變有序 ​

2.1 常見排序演算法 ​

2.2 為什麼快速排序「快」？ ​

3. 遞迴：自己呼叫自己 ​

3.1 遞迴的本質 ​

3.2 遞迴 vs 迭代 ​

4. 貪婪演算法：每步選最優 ​

4.1 貪婪的思想 ​

4.2 貪婪的侷限性 ​

5. 演算法設計範式 ​

6. 總結：演算法是解決問題的藝術 ​

延伸閱讀 ​

演算法思維入門

0. 全景圖：演算法是什麼？

1. 二分搜尋：每次排除一半

1.1 二分搜尋的原理

1.2 為什麼二分搜尋這麼快？

2. 排序：將無序變有序

2.1 常見排序演算法

2.2 為什麼快速排序「快」？

3. 遞迴：自己呼叫自己

3.1 遞迴的本質

3.2 遞迴 vs 迭代

4. 貪婪演算法：每步選最優

4.1 貪婪的思想

4.2 貪婪的侷限性

5. 演算法設計範式

6. 總結：演算法是解決問題的藝術

延伸閱讀