介绍分治法的基本思想、时间复杂度分析以及主定理的应用
分治法
分治法的时间复杂度分析
分治法的时间复杂度表达式
$$T(n) = aT(n/b) + f(n)$$
- 其中
- a：子问题的个数
- n/b：每个子问题的规模
- f(n)：分解问题和合并结果的时间复杂度
主定理
- 主定理是解决分治算法时间复杂度的强大工具，设$T(n) = aT(n/b) + f(n)$,其中$a \geq 1， \space b > 1 $，则
- 情况1：$f(n) = O(n^c)$，其中$c < log_b(a)$
- 此时$T(N) = \Theta(n^{log_b(a)})$
- 即此时递归树的叶子节点主导了时间复杂度
- 情况2：$f(n) = \Theta(n^c)$，其中$c = log_b(a)0$
- 此时$T(n) = \Theta(n^c \times log \space n)$
- 每层的工作量相同，总共有$log \space n$层
- 情况3：$f(n) = \Omega(n^c)$，其中$c > log_b(a)$
- 此时$T(n) = \Theta(n \space log \space n)$