A Level 電腦科學 (9618) 學習筆記

第 19 章：運算思維與問題解決 (A Level 內容)

歡迎來到 A Level 電腦科學中最令人興奮且實用的章節！
運算思維的核心在於如何分析複雜問題，並設計出電腦能夠執行的高效解決方案。這不僅僅是撰寫程式碼，更是要像電腦科學家一樣去思考。

在本章中，我們將加深對進階演算法（如搜尋與排序）的理解，探索稱為抽象資料類型（ADTs）的強大資料結構，並掌握優雅的遞迴技術。這些技能是建立高效且具擴展性軟體解決方案的基礎。

19.1 演算法與效率

19.1.1 進階搜尋方法

我們已經知道如何搜尋資料，但現在我們要比較兩種核心方法：

線性搜尋 (Linear Search)

這是最簡單的搜尋方法。

  • 運作方式： 從第一個元素開始，順序檢查列表中的每一項，直到找到目標項目或到達列表末端。
  • 適用場景： 非常適合小型列表或未經排序的列表。
  • 比喻：想像在裝滿未整理文件的鞋盒中找一張特定的收據，你必須逐一檢查。
二分搜尋 (Binary Search)

二分搜尋的效率高出許多，但它有一個關鍵的前提條件。

使用條件： 資料結構（例如陣列或列表）必須經過排序。

逐步過程：

  1. 找到列表的中間項目。
  2. 將中間項目與目標值進行比較。
  3. 如果兩者相符，搜尋完成。
  4. 如果目標值較小，忽略列表的右半部（以及中間項目）。
  5. 如果目標值較大，忽略列表的左半部（以及中間項目）。
  6. 在剩餘的半部重複此過程，直到找到項目或子集為空。

比喻：像「20 個問題」的猜謎遊戲。每一次比較都會將搜尋範圍縮小一半。

效能： 由於列表在每個步驟中都被減半，隨著資料項目 (N) 的增加，二分搜尋的表現遠優於線性搜尋。

快速回顧：搜尋

線性搜尋： 簡單，適用於未排序資料。對於大型 N 來說較慢。

二分搜尋： 必須排序。對於大型 N 來說非常快。

19.1.2 排序演算法

排序是將資料按特定順序排列的過程。你必須能夠編寫並追蹤兩種基本排序演算法的虛擬碼：

氣泡排序 (Bubble Sort)

這通常是最容易理解的演算法，但效率也是最低的。

  • 運作方式： 反覆遍歷列表，比較相鄰元素，如果順序錯誤則進行交換。
  • 效率： 在最壞的情況下（例如列表是反向排序的），氣泡排序需要很長時間，因為涉及大量的交換。
  • 記憶小撇步：想像較輕（較小）的氣泡浮到上方（或較重的項目沉到下方），經過多輪掃描完成排序。
插入排序 (Insertion Sort)

插入排序通常比氣泡排序更有效率，特別是對於小型或部分已排序的列表。

  • 運作方式： 每次處理一個項目，將其建立成最終的已排序陣列。它會迭代輸入元素，並將每個元素插入到已排序部分中的正確位置。
  • 比喻：整理手中的撲克牌。你保持手中的牌已排序，每拿到一張新牌，就找到合適的位置將其插入。

你知道嗎？ 資料的初始順序會顯著影響排序常式的執行時間。如果資料已經大致有序，插入排序的速度會比氣泡排序快得多。

19.1.3 抽象資料類型 (ADTs)

抽象資料類型 (ADT) 是資料結構的數學模型。關鍵在於，它定義了資料儲存機制以及可以對該資料執行的操作集合。

使用 ADT 的主要優點在於抽象化 (Abstraction)：我們只關心資料結構「做什麼」（其操作），而不關心它是「如何實現的」（例如使用陣列還是鏈結串列）。

堆疊 (Stack)
  • 原則： LIFO (後進先出)。最後加入的項目是第一個被移除的。
  • 關鍵操作：
    • PUSH： 將項目加入堆疊頂端。
    • POP： 從堆疊頂端移除並返回該項目。
  • 實現： 通常使用陣列實現，並配合一個指標（或索引）來追蹤「堆疊頂端」(Top of Stack) 的位置。
  • 應用：用於遞迴（呼叫堆疊）、軟體的復原 (Undo) 機制，以及表達式求值。
佇列 (Queue)
  • 原則： FIFO (先進先出)。第一個加入的項目是第一個被移除的。
  • 關鍵操作：
    • ENQUEUE： 將項目加入佇列尾端。
    • DEQUEUE： 從佇列前端移除並返回該項目。
  • 實現： 通常使用陣列實現，需要分別追蹤「前端」(Front) 和「尾端」(Rear) 的指標。
  • 應用：用於作業系統（任務排程）、列印緩衝區 (Print Spooling) 以及模擬。
鏈結串列 (Linked List)
  • 概念： 一種由節點 (Node) 組成的動態結構。每個節點包含資料項以及指向序列中下一個節點的指標（或參照）。
  • 優點： 插入和刪除操作非常高效，因為你只需要更新指標，而不需要像陣列那樣移動整個資料集。
  • 實現： 可以使用兩個並行陣列實現（一個用於資料，一個用於指標/索引）。
  • 關鍵操作： 應編寫演算法透過指標遍歷列表來尋找、插入和刪除項目。
二元樹 (Binary Tree, BT)
  • 概念： 一種層次結構，其中每個節點最多有兩個子節點（左子節點和右子節點）。
  • 組織： 節點左子樹中的資料總是小於節點資料；右子樹中的資料總是較大。這稱為二元搜尋樹 (BST)。
  • 關鍵操作： 應編寫演算法來尋找、插入和刪除項目，依靠層次結構來加快搜尋速度（效能與二分搜尋相似）。
圖形 (Graph)

圖形是一種用於建模物件之間關係的 ADT。

  • 關鍵特徵：
    圖形由頂點 (Vertices)（節點）和邊 (Edges)（連接或鏈結）組成。
    邊可以是有向的（單向）或無向的（雙向），並且可能具有權重（成本）。
  • 應用： 圖形非常適合用於地圖繪製、網路拓撲、路由演算法（如 GPS 中使用的演算法）以及社群媒體中的關係建模。

注意：雖然圖形在 AI（人工智慧，特別是 18.1 節）中很重要，但你只需要了解圖形 ADT 的關鍵特徵並能說明其應用理由，不需要編寫其結構或遍歷的程式碼，除非是 18.1 節中可能學到的演算法（A* 和 Dijkstra）。

19.1.4 使用 Big O 符號比較演算法

執行相同任務（如搜尋或排序）的不同演算法，可以根據其時間複雜度（速度）和空間複雜度（記憶體使用量）來比較。這使用 Big O 符號來量化。

什麼是 Big O？

Big O 符號描述了當參數趨向特定值或無窮大時，函數的極限行為。在電腦科學中，它告訴我們隨著輸入大小 (\(N\)) 變得非常大時，演算法的效能（時間/記憶體）如何擴展。

常見複雜度：
  • \(O(1)\) - 常數時間： 無論輸入大小如何，操作所需時間都相同。
    例子：透過索引存取陣列中的元素。
  • \(O(\log N)\) - 對數時間： 時間增加非常緩慢；每個步驟的工作量都會減少。
    例子：二分搜尋。如果你將輸入大小加倍，只需要多執行一個步驟。
  • \(O(N)\) - 線性時間： 所需時間與輸入大小成正比增加。
    例子：線性搜尋。如果你將輸入大小加倍，所需時間也會加倍。
  • \(O(N^2)\) - 二次時間： 所需時間呈現指數級增長（N 乘以 N）。這通常發生在演算法對資料使用巢狀迴圈時。
    例子：氣泡排序和插入排序（在最壞情況下）。

重點總結： 當 N 很大時，\(O(\log N)\) 遠優於 \(O(N)\)，後者又遠優於 \(O(N^2)\)。了解 Big O 有助於我們說明選用特定演算法的理由（例如，在大型已排序資料庫中選擇二分搜尋而非線性搜尋）。

19.1 節重點

必須根據資料結構（是否已排序？）和預期的輸入大小 (N) 來選擇高效的演算法。Big O 符號是衡量這種效率的標準工具。

19.2 遞迴 (Recursion)

遞迴是一種強大的技術，透過將問題分解為相同問題的較小實例，直到達到可輕易解決的簡單情況為止。

遞迴的核心特徵

每個成功的遞迴常式都必須具備兩個基本要素：

  1. 基底情況 (Base Case / 終止條件)： 這是停止遞迴的條件。當滿足基底情況時，函式會返回一個值，而不再進行遞迴呼叫。如果沒有基底情況，函式將無限執行，導致堆疊溢位 (Stack Overflow) 錯誤。
  2. 遞迴步驟 (Recursive Step)： 這是函式呼叫自身的地方，通常參數會比之前更接近基底情況，從而逐步縮小問題規模。

例子：計算階乘 (N!)

\(N!\) 的定義為： \[N! = N \times (N-1)! \quad \text{對於 } N > 0\] \[0! = 1 \quad \text{(基底情況)}\]

虛擬碼（簡化版）： 

FUNCTION Factorial(N: INTEGER) RETURNS INTEGER
    IF N = 0 THEN
        RETURN 1       <-- 基底情況
    ELSE
        RETURN N * Factorial(N - 1) <-- 遞迴步驟
    ENDIF
ENDFUNCTION

追蹤與解開遞迴 (堆疊的使用)

當函式被呼叫時，系統會建立一個啟動記錄 (Activation Record)（或稱堆疊幀），儲存區域變數、參數和返回位址。這些記錄會被放入呼叫堆疊 (Call Stack)（一種堆疊 ADT）中。

  • 當執行遞迴呼叫時，新的啟動記錄會被推入 (Push) 堆疊。
  • 此過程持續進行，直到達到基底情況。
  • 一旦觸及基底情況，解開 (Unwinding) 過程便開始：結果會從位於堆疊頂端的函式呼叫中返回，該啟動記錄隨即被彈出 (Pop)。此過程持續向後進行，直到原始函式呼叫返回其最終結果。

編譯器的工作： 編譯器必須確保遞迴程式碼能夠正確管理這個呼叫堆疊，處理執行與解開過程中啟動記錄的推入與彈出。

遞迴何時有益？

雖然任何遞迴演算法都可以改寫為迭代形式（使用迴圈），但遞迴之所以有益，是因為它通常能產出如下程式碼：

  • 更優雅： 對於複雜問題，特別是涉及樹狀結構（如二元樹）或數學序列（如階乘）的問題，遞迴能以更自然、簡潔的方式表達。
  • 更易於閱讀/證明： 對於天生具備遞迴性質的問題，程式碼直接反映了數學定義，使得驗證其正確性變得更容易。

常見錯誤：忘記基底情況！這會導致無限遞迴，並因耗盡堆疊記憶體而使程式崩潰。

19.2 節重點

遞迴是用自身來定義函式。它很強大，但需要嚴格的基底情況來防止無限迴圈。呼叫堆疊透過解開過程來管理執行與結果。


完成這次對演算法和遞迴的深入探討，做得好！這些都是 A Level 的核心概念，也是進階電腦科學的基石。請繼續練習追蹤遞迴函式並計算 Big O 複雜度——你一定沒問題的！