主定理
介绍
在分治算法中，我们经常需要分析递归算法的时间复杂度。主定理（Master Theorem）提供了一种快速计算分治算法时间复杂度的通用方法。它适用于形如以下递归关系的算法：
T(n) = a * T(n/b) + f(n)
其中：
a是子问题的数量。n/b是每个子问题的规模。f(n)是合并子问题结果的时间复杂度。
主定理帮助我们根据 a、b 和 f(n) 的关系，快速得出 T(n) 的渐近复杂度。
主定理的形式
主定理分为三种情况，具体取决于 f(n) 与 n^(log_b(a)) 的关系：
- 情况一：如果
f(n) = O(n^(log_b(a) - ε))，其中ε > 0，则T(n) = Θ(n^(log_b(a)))。 - 情况二：如果
f(n) = Θ(n^(log_b(a)) * log^k(n))，其中k ≥ 0，则T(n) = Θ(n^(log_b(a)) * log^(k+1)(n))。 - 情况三：如果
f(n) = Ω(n^(log_b(a) + ε))，其中ε > 0，并且满足正则条件a * f(n/b) ≤ c * f(n)（c < 1），则T(n) = Θ(f(n))。
提示
主定理的三种情况分别对应 f(n) 的增长率与 n^(log_b(a)) 的关系：
- 情况一：
f(n)增长较慢。 - 情况二：
f(n)增长相同。 - 情况三：
f(n)增长较快。
实际案例
案例一：归并排序
归并排序是一种典型的分治算法，其递归关系为：
T(n) = 2 * T(n/2) + O(n)
其中：
a = 2，b = 2，f(n) = O(n)。- 计算
n^(log_b(a)) = n^(log_2(2)) = n^1 = n。
由于 f(n) = O(n) 与 n^(log_b(a)) 相同，属于情况二，因此：
T(n) = Θ(n * log(n))
案例二：二分查找
二分查找的递归关系为：
T(n) = T(n/2) + O(1)
其中：
a = 1，b = 2，f(n) = O(1)。- 计算
n^(log_b(a)) = n^(log_2(1)) = n^0 = 1。
由于 f(n) = O(1) 与 n^(log_b(a)) 相同，属于情况二，因此：
T(n) = Θ(log(n))
代码示例
以下是一个简单的分治算法示例：计算数组的最大值。
python
def find_max(arr, low, high):
if low == high:
return arr[low]
mid = (low + high) // 2
left_max = find_max(arr, low, mid)
right_max = find_max(arr, mid + 1, high)
return max(left_max, right_max)
# 示例输入
arr = [3, 5, 1, 7, 9, 2]
print(find_max(arr, 0, len(arr) - 1)) # 输出：9
该算法的时间复杂度分析：
- 递归关系：
T(n) = 2 * T(n/2) + O(1)。 - 根据主定理，
a = 2，b = 2，f(n) = O(1)。 - 计算
n^(log_b(a)) = n^(log_2(2)) = n。 - 由于
f(n) = O(1)比n增长慢，属于情况一，因此T(n) = Θ(n)。
总结
主定理是分析分治算法时间复杂度的强大工具。通过识别递归关系中的 a、b 和 f(n)，我们可以快速得出算法的渐近复杂度。以下是主定理的三种情况的总结：
- 情况一：
f(n)增长较慢，时间复杂度由子问题决定。 - 情况二：
f(n)增长相同，时间复杂度包含对数因子。 - 情况三：
f(n)增长较快，时间复杂度由合并步骤决定。
附加资源与练习
练习
- 分析快速排序的时间复杂度。
- 编写一个分治算法来计算数组的最小值，并分析其时间复杂度。
资源
警告
主定理并不适用于所有递归关系。如果递归关系不符合 T(n) = a * T(n/b) + f(n) 的形式，则需要使用其他方法（如递归树或代入法）进行分析。