文章目录
  1. 1. 什么是主定理
  2. 2. 用主定理搞事情
    1. 2.1. 二分查找
    2. 2.2. 归并排序
    3. 2.3. 二叉树遍历

在前面讲到的Big-Oh算法复杂度分析的文章时,我曾经提到过主定理,既然主定理是奠定算法分析尤其是递归算法的理论基石,那么就有必要拿出来单独讲一讲,即使我们是属于拿来主义的工程派,理解使用工具的理论根据也是有益无害的吧?当然在最后我们会总结几个工程常用的分析算法复杂度的例子。

什么是主定理

主定理来源于算法导论,是在第四章介绍分治法时适时引出的。
wikipedia这样说

主定理的描述是这样的:
令$a \geq 1$, $b > 1$的常数, $f(n)$为一个函数, $T(n)$的递归定义式如下:
$$T(n) = aT(n/b) + f(n)$$,
这里我们解释$n/b$为 $n/b$的最近的整数,即向上取整或者是向下取整。
那么我们根据$f(n)$的情况会有下面三个$T(n)$的函数渐进边界。

  1. 如果存在常数$\varepsilon$ $f(n) = O(n^{log_b^{a-\varepsilon}})$ 我们有
    $$T(n) = \Theta(n^{log_b^a})$$
  2. 如果 $f(n) = \Theta(n^{log_b^a})$, 那么我们有
    $$T(n) = \Theta(n^{log_b^a}lg^n)$$
  3. 如果存在常数$\varepsilon$使得 $f(n) = \Omega(n^{log_b^{a+\varepsilon}})$, 并且如果存在常数 $c < 1$ 以及当$n$足够大的时候,使得 $af(n/b) \leq cf(n)$

注意到定理中讨论的情况其实有个关键的分割点是讨论 $f(n)$ 与 $n^{log_b^a}$ 的大小关系。
第一种情况其实是$f(n)$小于 $n^{log_b^a}$的情况
第二种情况是等于的情况
第三种情况是大于的情况

用主定理搞事情

首先是

二分查找

由于是已经排好序的列表,二分查找在算法描述上实际上是在查找的时候将原问题(在长度为n的列表查找)分解为通过比较pivot的大小(操作复杂度$O(1)$)转化为一个更小的子问题(在长度为n/2的列表查找),很自然的我们有二分查找的递归表达式$$T(n) = T(n/2) + O(1)$$
下面我们使用主定理,首先看下$f(n)$ 实际上$f(n) = O(n^0)$, 其次我们看下$a = 1, b = 2$ $log_2^1 = 0$ 也就是 第二种等于的情况,因此我们有 $T(n) = O(n^{log_2^1}log^n) = O(log^n)$

归并排序

从归并算法的描述来看,选择pivot后将原问题(长度为n的排序问题)转化为 两个长度为$n/2$的子问题,和一个两个排好序的列表的合并问题(时间复杂度为:$O(n)$)。自然地我们有归并排序的递归表达式为 $$T(n) = 2T(n/2) + O(n)$$
下面我们使用主定理, 首先$f(n)=O(n^1)$ , $a = 2, b = 2$ $log_2^2 = 1$ 也就是第二种等于的情况, 因此我们有 $T(n) = O(n^{log_2^2}log^n) = O(nlog^n)$

二叉树遍历

从算法描述上看,二叉树遍历实际是将一整棵二叉树遍历问题分解为分别遍历左子树($O(n/2)$),右子树($O(n/2)$),以及根节点($O(1)$)的子问题,因此递归表达式为$$T(n) = 2T(n/2) + O(1)$$
下面我们使用主定理, 首先$f(n) = O(n^0)$, $a =2, b = 2$ $log_2^2 = 1$ 也就是第一种情况,因此我们有$$T(n) = O(n^{log_2^2}) = O(n)$$

文章目录
  1. 1. 什么是主定理
  2. 2. 用主定理搞事情
    1. 2.1. 二分查找
    2. 2.2. 归并排序
    3. 2.3. 二叉树遍历