八、算法設計與分析

1 算法設計與分析的基本概念

1.1 算法

定義：算法是對特定問題求解步驟的一種描述，是有限指令序列，每條指令表示一個或多個操作。
特性：
- 有窮性：算法需在有限步驟和時間內結束。
- 確定性：指令無歧義，相同輸入輸出唯一。
- 可行性：操作可通過基本運算有限次實現。
- 輸入：零個或多個輸入，來自特定對象集合。
- 輸出：一個或多個輸出，與輸入有特定關系。

1.2 算法設計

目標： correctness（正確性）、readability（可讀性）、robustness（健壯性）、high efficiency（高效性）。
常用設計技術： divide and conquer（分治法）、dynamic programming（動態規劃法）、greedy algorithm（貪心法）、backtracking（回溯法）、branch and bound（分支限界法）、probabilistic algorithm（概率算法）、approximation algorithm（近似算法）。

1.3 算法分析

定義：估算算法所需資源，主要有時間復雜度和空間復雜度。
重要性：幫助選擇最高效的算法。

1.4 算法的表示

自然語言：易懂但易產生歧義，冗長。
流程圖：直觀易懂，但嚴密性和靈活性不足。
程序設計語言：可直接執行，但抽象性差，細節繁瑣。
偽代碼：結合自然語言和程序設計語言，簡潔明了，適合表達算法邏輯，本章采用 C 語言表示算法。

2 算法分析基礎

2.1 時間復雜度

時間復雜度分析用于評估算法的運行時間，主要分為三種情況：

最好情況：算法執行時間最少的情況。
最壞情況：算法執行時間最多的情況。
平均情況：算法的平均執行時間，計算公式為 $\sum_{i=1}^{m} p_i \cdot t_i$ ，其中 $p_i$ 是輸入的概率， $t_i$ 是輸入的執行時間，輸入分為 m 類。

2.2 漸進符號

漸進符號用于描述函數的增長速率：

O 記號：表示算法運行時間的上界。
Ω 記號：表示算法運行時間的下界。
Θ 記號：同時表示算法運行時間的上界和下界。

2.3 遞歸式

遞歸式用于描述遞歸算法的時間復雜度。常見的求解方法包括：

展開法：通過逐層展開遞歸式，得到一個求和表達式，然后求解。
代換法：猜測解的形式，然后用數學歸納法證明。
遞歸樹法：構造遞歸樹，將遞歸調用的代價累加到遞歸樹的每一層。
主方法：適用于形式為 T(n) = aT(n/b) + f(n) 的遞歸式，其中 a ≥ 1，b > 1，f(n) 是一個遞增函數。

3 分治法

3.1 遞歸的概念

遞歸是函數直接或間接調用自身的一種方法。遞歸有兩個基本要素：邊界條件（決定遞歸何時終止）和遞歸模式（如何將問題分解為更小的子問題）。例如，階乘函數可以用遞歸定義為：

$\begin{cases} 1 & \text{if } n = 0 \\ n \times (n-1)! & \text{if } n > 0 \end{cases}$

對應的 C 代碼如下：

int Factorial(int n) {if (n == 0)return 1;elsereturn n * Factorial(n - 1);
}

3.2 分治法的基本思想

分治法的核心思想是將一個難以直接解決的大問題分解成規模較小的子問題，遞歸地解決這些子問題，然后將子問題的解合并成原問題的解。分治法在每一層遞歸上都有三個步驟：

分解：將原問題分解成多個較小的子問題。
求解：遞歸地求解各個子問題。若子問題足夠小，則直接求解。
合并：將子問題的解合并成原問題的解。

3.3 分治法的典型實例

3.3.1 歸并排序

歸并排序是分治法的經典應用，其基本思想是將待排序元素分成大小大致相同的兩個子序列，分別對這兩個子序列遞歸地排序，最后將排好序的子序列合并成一個有序序列。

歸并排序的時間復雜度為 $\log n)$ 。

3.3.2 最大子段和問題

給定一個由 n 個整數（可能有負整數）組成的序列 $a1,a2,…,ana_1, a_2, \ldots, a_n$ ，求該序列形如 $∑k=ijak\sum_{k=i}^j a_k$ 的子段和的最大值。最大子段和問題的分治法策略如下：

分解：將序列從中間位置分為兩段，分別求出左半段和右半段的最大子段和。
求解：遞歸地求解左半段和右半段的最大子段和。
合并：比較左半段、右半段和跨越中間位置的子段和的最大值，取三者中的最大值作為原問題的解。

4 動態規劃法

4.1 動態規劃法的基本思想

動態規劃法與分治法類似，基本思想是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動態規劃法求解的問題，經分解得到的子問題往往不是互相獨立的，而是具有重疊子問題的性質。因此，動態規劃法通過記錄已經求解過的子問題的解（通常用表格記錄），以避免重復計算，從而提高效率。

動態規劃法通常用于求解具有某種最優性質的問題，通過以下步驟實現：

找出最優解的性質，并刻畫其結構特征。
遞歸地定義最優值。
以自底向上的方式計算最優值。
根據計算最優值時得到的信息，構造一個最優解。

當只需要求出最優值時，步驟（1）-（3）是動態規劃算法的基本步驟。若需要構造最優解，則必須執行步驟（4）。

4.2 動態規劃法的典型實例

4.2.1 0-1 背包問題

動態規劃法通過以下步驟解決 0-1 背包問題：

刻畫 0-1 背包問題的最優解結構
遞歸定義最優值
計算背包問題的最優值
根據最優解構造最優解

4.2.2 最長公共子序列（LCS）問題

LCS 問題的最優子結構
遞歸定義最優值
計算最優值
構造最優解

5 貪心法

5.1 貪心法的基本思想

貪心法是一種算法設計技術，常用于解決優化問題。與動態規劃法不同，貪心法通過一系列局部最優選擇來構建全局最優解。貪心法的特點如下：

局部最優選擇：貪心法在每一步選擇中都做出局部最優的選擇，而不從全局考慮。這種局部最優選擇并不能保證總能得到全局最優解，但在許多情況下可以得到較好的近似解。
不可回溯性：一旦做出選擇，就不會再改變，即使后續發現有更好的選擇也不會回溯。

貪心法適用的問題通常具有以下兩個重要性質：

最優子結構：問題的最優解包含其子問題的最優解。
貪心選擇性質：問題的整體最優解可以通過一系列局部最優選擇得到。

5.2 貪心法的典型實例

5.2.1 活動選擇問題

活動選擇問題要求從多個活動集合中選擇最大數量的相容活動。貪心算法通過按活動結束時間排序，每次選擇最早結束的活動，并跳過與之沖突的活動。

5.2.2 背包問題

背包問題允許將物品部分裝入背包，目標是使背包中物品的總價值最大。貪心策略包括：

按最大價值優先：先放入價值最大的物品。
按最小重量優先：先放入重量最小的物品。
按最大單位重量價值優先：先放入單位重量價值最大的物品。

貪心算法的 C 代碼如下：

float* GreedyKnapsack(int n, int W, int* Weights, float* Values, float* V) {float* x = (float*)malloc(sizeof(float) * n);for (int i = 0; i < n; i++)x[i] = 0;for (int i = 0; i < n; i++) {if (Weights[i] <= W) { // 如果背包剩余容量可以裝下該物品x[i] = 1;W -= Weights[i];} elsebreak;}if (i < n) { // 如果還有物品可以部分裝入背包x[i] = (float)W / Weights[i];}return x;
}