2-1 算法的時間復雜度分析

2.1.1 輸入規模與基本語句

• 輸入規模：算法處理數據的規模，通常用 n 表示。

• 基本語句：執行次數與輸入規模直接相關的關鍵操作。

• 例2.1 順序查找

  int SeqSearch(int A[], int n, int k) {  for (int i = 0; i < n; i++)  if (A[i] == k) break;  if (i == n) return 0;  else return (i + 1);  
  }
  

  • 輸入規模 n；基本語句是“比較 A[i] == k”

2.1.2 漸近分析

• 大 O、大 Ω、大 Θ

  • T(n)=O(f(n))：? c, n?, ? n ≥ n?, T(n) ≤ c·f(n)

  • T(n)=Ω(f(n))：? c, n?, ? n ≥ n?, T(n) ≥ c·f(n)

  • T(n)=Θ(f(n))：同時滿足 O(f(n)) 和 Ω(f(n))

• 例：若 T(n) ≤ 100n + n 則 T(n)=O(n)

  • 取 n?=5, c=101, 則 ? n ≥ 5, T(n) ≤ 101n → O(n)

• 常見增長階
  1 < log n < n < n log n < n2 < n3 < … < 2? < n!

• 例2.4 合并算法

  void Union(int A[], int n, int B[], int m, int C[]) {int i=0, j=0, k=0;while (i<n && j<m) {if (A[i] <= B[j]) C[k++] = A[i++];else C[k++] = B[j++];}while (i<n) C[k++] = A[i++];while (j<m) C[k++] = B[j++];
  }
  

  • 時間復雜度 O(n + m)

2.1.3 最好、最壞和平均情況

• 當算法執行代價依賴于不同輸入時，需要分別分析：

  • 最好情況：最少操作次數；

  • 最壞情況：最多操作次數；

  • 平均情況：所有輸入實例上的平均操作次數。

• 順序查找例

  • 最好：第1個元素即中，比較1次；

  • 最壞：未找到或在末尾，比較n次；

  • 平均：約(n + 1)/2次

---

2-2 算法的空間復雜度分析

• 空間復雜度 = 輸入/輸出數據占用 + 算法本身占用 + 輔助空間

  1. 輸入/輸出數據：題目本身的數據結構；

  2. 算法本身：局部變量、常量，通常為 O(1)；

  3. 輔助空間：臨時數組、遞歸棧等。

• 示例

  • CommonFactor 求最大公約數：僅用常數級局部變量，O(1)；

  • BubbleSort：只用固定數量的索引和臨時變量，O(1)；

  • Merge：需要長度為 n 的臨時數組，O(n)。

---

2-3 算法的實驗分析

• 實驗分析：將算法實現為程序，上機運行，實際測算時空開銷

• 常用度量方法

  1. 計數法：插入計數器，記錄關鍵語句執行次數；

  2. 計時法：記錄程序段開始和結束時間，計算時間差。

• 例 BubbleSort 實驗

  void BubbleSort(int r[], int n) {int j, temp, count1=0, count2=0, bound, exchange=n-1;while (exchange != 0) {bound = exchange; exchange = 0;for (j = 0; j < bound; j++)if (++count1 && r[j] > r[j+1]) {temp = r[j]; r[j] = r[j+1]; r[j+1] = temp;count2 += 3; exchange = j;}}cout<<"比較次數="<<count1<<"，移動次數="<<count2<<endl;
  }
  

  • 目的：統計比較次數和移動次數

• Collatz 過程實驗

  • 規則：n 為奇數 → 3n+1，否則 → n/2，直到 n=1；

  • 例 n=9：{9,28,14,…,1}；

  • 例 n=27：77步到9232，再32步到1。

---

2-4 拓展與演練：最優算法與下界

• 下界 Ω 表示法
  若 ? c, n?, ? n ≥ n?, T(n) ≥ c·g(n)，則 T(n)=Ω(g(n))，g(n) 是問題的時間下界

• 最優算法
  如果問題已知下界 g(n)，且算法滿足 T(n)=Θ(g(n))，則該算法為最優。

• 例2.10 最小值算法

  int ArrayMin(int a[], int n) {int min = a[0];for (int i = 1; i < n; i++)if (a[i] < min) min = a[i];return min;
  }
  

  • 比較次數下界 Ω(n)，算法時間 O(n)，故為最優。