第2章 算法分析基础

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 < n² < n³ < … < 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)，故为最优。