1-1 什么是算法

見識算法

• 算法是計算機科學的基石：從古代算術到現代計算機，算法始終是解決問題的核心。

算法的起源

• 張蒼《九章算術》：創立了機械化算法體系（如“合分術”分數相加算法）。

• 歐幾里得《幾何原本》：奠定了邏輯演繹體系，為后世算法理論提供嚴密的數學基礎。

---

1.1.1 算法的定義

• 算法：對特定問題求解步驟的一種描述，是指令的有限序列。

• 三要素：

  1. 有窮性：算法必須在有限步內終止，防止出現死循環或無限運行，以保證能在實際環境中獲得結果；

  2. 確定性：每一步都有唯一明確定義，避免歧義和不一致，確保重復執行時輸出一致；

  3. 可行性：每一步都能在有限時間和空間資源下執行，保證算法在實際計算環境中可實現。

Problem 與 Instance

• Problem（問題）：規定輸入與輸出之間關系的抽象集合；

• Instance（實例）：具體的輸入數據集合。

• 排序問題示例：

  • 輸入：<31, 41, 59, 26, 41, 58>

  • 輸出：<26, 31, 41, 41, 58, 59>

示例題目

• 例1.1 設計算法求兩個自然數的最大公約數

  • 思路（質因數分解法）：

    1. 找出 m 的所有質因子；

    2. 找出 n 的所有質因子；

    3. 求交集并相乘。

  • 缺陷：分解過程時間復雜度高，因子枚舉不確定，難以擴展大數運算，且分解失敗時無法輸出。

• 例1.2 歐幾里德算法——輾轉相除法求最大公約數

  • 步驟：

    1. r = m % n

    2. 若 r = 0，則輸出 n；否則 m ← n，n ← r，轉步驟1。

  • 優點：時間復雜度 O(log min(m,n))，保證有窮性和可行性，簡單易實現，確定性強。

---

1.1.2 算法的描述方法

1. 自然語言

   • 優點：通俗易懂；缺點：描述不夠嚴密，易產生歧義。

2. 程序流程圖

   • 優點：結構清晰、直觀；缺點：難表達復雜邏輯，維護和修改成本高。

3. 偽代碼

   • 優點：兼顧可讀性與嚴密性，可快速轉化為程序；缺點：語法非標準，不同風格可能導致理解成本。

示例偽代碼題目

• （1）瓶子 A 與 B 液體互換

  1. C ← A

  2. A ← B

  3. B ← C

• （2）三個數由小到大排序

  1. 若 x > y，則交換；

  2. 若 z < x，則循環交換；否則若 z < y，則交換；

  3. 輸出 x, y, z。

• （3）在 n 元素集合中查找最大值

  1. max ← a[1]；

  2. i ← 2；

  3. 當 i ≤ n 時：若 a[i] > max，則 max ← a[i]；i ← i + 1；

  4. 輸出 max。

---

1.1.3 算法在問題求解中的地位

1. 人 分析問題并設計算法；

2. 人 編寫程序；

3. 機器 執行程序，得到結果。

強調算法設計是溝通人和機器的橋梁，決定程序效率與可維護性。

---

1-2 什么是好算法

1.2.1 如何評價算法

1. 正確性：算法必須對所有合法輸入產生正確輸出，否則無法信賴；

2. 健壯性：能識別和處理無效或異常輸入，避免程序崩潰或產生誤導性結果；

3. 可理解性：清晰的邏輯結構和注釋便于他人閱讀、調試和維護，降低開發成本；

4. 抽象分級：合理劃分模塊和層次，符合人類認知規律（7±2 原則），提高復用性；

5. 高效性：兼顧時間復雜度和空間復雜度，使算法在大規模數據或復雜環境中仍能快速運行；

6. 可擴展性：便于后續功能擴展或性能優化，以適應需求變化。

案例對比：當 n = 103 時，冒泡排序約需 0.01 s；當 n = 10? 時，快速排序僅需約 0.02 s，而冒泡排序則超過 102 s，效率差異隨規模增長指數級放大。

---

1-3 為什么要學習和研究算法

1.3.1 算法研究推動計算機技術發展

• 查找問題：二分查找 O(log n)，將線性查找 O(n) 降為對數級，大幅提升檢索效率；

• 圖問題：Dijkstra 算法解決最短路徑，實現地圖導航、網絡路由等核心功能；

• 組合優化：背包問題、旅行商問題等，影響資源分配與調度系統設計。

多數現代應用（搜索引擎、社交網絡、電子商務）都依賴高效算法來支撐海量數據處理。

1.3.2 算法訓練提升計算思維能力

• 模型化：將現實問題抽象為數學模型，有助于使用已知算法求解；

• 抽象思考：在機外表示與機內表示間切換，理解問題核心；

• 形式化：將解題思路轉化為偽代碼或程序，保證邏輯嚴密性和可執行性。

思維收益：培養分治、貪心、動態規劃等思維模式，提高解決復雜問題的條理性與創造力。

1.3.3 程序員必學算法的程度

Algorithm + Data Structures = Programs

• 基礎功底：理解算法思想有助合理選擇和組合數據結構；

• 應用層面：不必精通所有算法，但應熟練掌握常用排序、查找、圖算法等；

• 高級優化：針對性能關鍵場景，掌握算法優化技巧能顯著提升系統效率。

---

1-4 如何設計算法

1.4.1 基本數據結構及其作用

• 集合：無序元素集合，支持高效去重和成員檢測；

• 線性結構：表、棧（LIFO）、隊列（FIFO），常用于任務調度和歷史記錄；

• 樹結構：二叉樹、平衡樹，用于層級數據組織與快速查找；

• 圖結構：鄰接表、鄰接矩陣，靈活表示網絡、依賴關系等。

1.4.2 常見問題類型與典型算法思路

• 查找：順序查找、二分查找、哈希查找；

• 排序：冒泡、插入、歸并、快速、堆排序；

• 圖：遍歷（DFS/BFS）、最短路徑、最小生成樹；

• 組合優化：動態規劃（背包、LCS）、分支限界；

• 數學：質數判定、最大公約數、快速冪；

• 幾何：凸包、掃描線。

1.4.3 算法設計一般流程

1. 問題分析：明確輸入輸出與性能約束；

2. 選擇技術：分治、動態規劃、貪心、回溯等；

3. 算法描述：偽代碼或流程圖；

4. 手動模擬：驗證正確性，修正邏輯；

5. 實現編碼：關注可讀性與可維護性；

6. 復雜度分析：評估時間和空間消耗；

7. 迭代優化：基于測試與分析，持續改進性能。

---

1-5 拓展與演練

1.5.1 圖靈獎獲獎者與算法貢獻

• Edsger Dijkstra：Dijkstra 最短路徑算法；

• Donald Knuth：《算法藝術》系列與文獻規范；

• Tony Hoare：快速排序；

• Stephen A. Cook：NP 完全性理論；

• Andrew Yao（姚期智）：通信復雜度與偽隨機數理論；

• Leslie Valiant：概率近似正確模型；

• Yoshua Bengio、Geoffrey Hinton、Yann LeCun：深度學習算法發展。

1.5.2 代碼優化技巧及原因

1. 常量計算：編譯期計算不變表達式，減少運行時開銷；

2. 算術優化：用加減或 Horner 法則替代乘除；

3. 位運算替代：如 x & 1 判斷奇偶，加快計算；

4. 避免重復：緩存中間結果，減少函數調用；

5. 共享子表達式：提高編譯器優化機會；

6. 邏輯短路：提前終止無必要判斷；

7. 合并循環：減少循環次數，降低控制開銷；

8. 循環不變式外提：移出循環內不變運算；

9. 合理條件順序：高概率分支優先，降低分支預測失敗；

10. 嵌套循環優化：優先減少內層循環次數。