第一章

第1章 算法引论

1.1 算法与程序

• 输入: 有零个或多个外部量作为算法的输入。
• 输出: 算法产生至少一个量作为输出。
• 确定性: 组成算法的每条指令清晰、无歧义。
• 有限性: 算法中每条指令的执行次数有限，执行每条指令的时间也有限。

区别:

• 算法: 满足上述性质的指令序列。
• 程序: 算法用某种程序设计语言的具体实现，程序可以不满足算法的有限性。

1.3 描述算法

算法的描述方法可以归纳为以下几种：

1. 自然语言
2. 图形，如流程图，图的描述与算法语言的描述对应
3. 算法语言，即计算机语言、程序设计语言、伪代码
4. 形式语言，用数学的方法，可以避免自然语言的二义性

1.4 算法复杂性分析

算法复杂性是算法运行所需要的计算机资源的量，包括：

• 时间复杂性: 需要时间资源的量
• 空间复杂性: 需要的空间资源的量

这个量只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。

表达式

• 设 N 为规模，I 为输入，A 为算法，C 为复杂性。
• 则: C = F(N, I, A)
  • 时间复杂性: T = T(N, I)
  • 空间复杂性: S = S(N, I)

复杂性函数具体化

• 假设有 k 种元运算：O1, O2, …, Ok
• 执行元运算所需时间分别为：t1, t2, …, tk
• Oi 运算次数为 ei
• 则 T(N, I) = Σ ti * ei
• 简化后 T = T(N, I) 仅与规模有关

算法复杂性函数示例

Algorithm lcsLength(x, y, b) 
1: m ← x.length - 1; 
2: n ← y.length - 1; 
3: c[i][0] = 0; c[0][i] = 0; 
4: for (int i = 1; i <= m; i++) 
5:     for (int j = 1; j <= n; j++) 
6:         if (x[i] == y[j]) 
7:             c[i][j] = c[i-1][j-1] + 1; 
8:             b[i][j] = 1; 
9:         else if (c[i-1][j] >= c[i][j-1]) 
10:             c[i][j] = c[i-1][j]; 
11:             b[i][j] = 2; 
12:         else 
13:             c[i][j] = c[i][j-1]; 
14:             b[i][j] = 3; 

最坏、最好、平均情况下的时间复杂性

• 最坏情况: Tmax(N)
• 最好情况: Tmin(N)
• 平均情况: 根据输入概率 P(I)

渐进性态与渐进表达式

• 渐进性态: 当 N 单调增加且趋于 ∞ 时，T(N) 也将单调增加趋于 ∞。
• 渐进表达式: 如果存在函数 T'(N)，使得 T(N) - T'(N) / T(N) → 0，则 T'(N) 是 T(N) 的渐进表达式。

示例: 3N² + 4N logN + 7 与 3N²

大O符号的定义与运算规则

定义

对于所有 N，f(N) ≥ 0，g(N) ≥ 0，如果存在常数 C 和自然数 N0，使得当 N ≥ N0 时:

f(N) ≤ C * g(N)

则称 f(N) 的阶至多是 O(g(N))，记为 f(N) = O(g(N))

运算规则

1. O(f) + O(g) = O(max(f, g))
2. O(f) + O(g) = O(f + g)
3. O(f) * O(g) = O(fg)
4. 如果 g(N) = O(f(N))，则 O(f) + O(g) = O(f)
5. O(Cf(N)) = O(f(N))，其中 C 是一个正的常数
6. O(f) = O(f)

例子

• f(n) = 20n² + 9n + 33
  • 取 n0 = 10，则当 n ≥ n0 时，f(n) ≤ 21n²
  • 令 C = 21, g(n) = n²
  • 所以 f(n) = O(n²)

Ω符号的定义

如果存在正的常数 C 和自然数 N0，使得当 N ≥ N0 时:

f(N) ≥ C * g(N)

则称函数 f(N) 的阶不低于 Ω(g(N))。

例子:

• f(n) = 5n + 2
  • 令 n0 = 0
  • 当 n ≥ n0 时，有 f(n) ≥ 5n = C1 * g(n)，其中 C1 = 5, g(n) = n
  • 所以 f(n) = Ω(n)

θ符号的定义

f(N) = θ(g(N)) 当且仅当 f(N) = O(g(N)) 且 f(N) = Ω(g(N))，此时称 f(N) 与 g(N) 同阶。

例子:

• f(n) = 5n + 2
  • f(n) = Ω(n)
  • f(n) = O(n)
  • 所以 f(n) = θ(n)

o符号的定义

对于任意给定的 ε > 0，存在正整数 N0，使得当 N ≥ N0 时有:

f(N) / (C * g(N)) ≤ ε

则称 f(N) = o(g(N))。

例子:

• 4N logN + 7 = o(3N² + 4N logN + 7)

常见复杂性函数

• 小规模数据复杂性增长图
• 中等规模数据复杂性增长图

非递归算法

1. for / while 循环
   • 循环体内计算时间 * 循环次数
2. 嵌套循环
   • 循环体内计算时间 * 所有循环次数
3. 顺序语句
   • 各语句计算时间相加
4. if-else语句
   • 取 if 和 else 语句计算时间的较大者

算法分析的基本法则

• 问题的计算时间下界为 Ω(f(n))，则计算时间复杂性为 O(f(n)) 的算法是最优算法。
  • 例如，排序问题的计算时间下界为 Ω(n log n)，计算时间复杂性为 O(n log n) 的排序算法是最优算法。堆排序算法是最优算法。

算法设计与分析的其他内容

• 证明正确性
• 分析算法
• 设计程序
• 理解问题
• 精确解或近似解
• 选择数据结构
• 算法设计策略
• 设计算法

小结

• 算法与程序的区别: 算法是解决问题的步骤和方法，程序是算法的具体实现。
• 算法设计: 包括设计算法、选择合适的数据结构、应用设计策略等。
• 算法分析: 评估算法的时间复杂性和空间复杂性，确保其在实际应用中的有效性和效率。