【Master Theorem主定理】递归时间复杂度分析


主定理的内容

《算法导论》中提到了主定理,用来分析分治方法带来的
主定理是解决递归时间复杂度的一种直接方法适合于以下类型的递推公式
$$T(n) = aT(n/b) + O(n^d) (a >= 1 且 b > 1)$$

其中$n$为问题规模,$a$为递推的子问题数量,$n/b$为每个子问题的规模(假设每个子问题的规模基本一样),$O(n^d)$为递推以外进行的计算工作量

那么问题的时间复杂度$T(n)$

  • 如果$a < b^d$,则$T(n) = O(n^d)$
  • 如果$a = b^d$,则$T(n) = O(n^dlogn)$
  • 如果$a > b^d$,则$T(n) = O(n^{log_b^a})$

说明:像$T(n) = T(\sqrt{n}) + 1$这个公式就不符合上面的递归类型,不过它可以通过换元得到上面形式,这里不再赘述

特殊情况f(n) = logn

$$T(n) = aT(n/b) + f(n)(a >= 1 且 b > 1)$$
Master’s theorem with $f(n)=logn$
MasterTheorem.pdf


Example

具体应用

例:二分查找

$T(n) = T(n/2) + O(n^0)$ 假设每个子问题的规模基本一样

$a = 1, b = 2, d = 0,b^d = 1$ ,所以 $T(n) = O(logn)$


例:归并排序

$T(n) = 2T(n/2) + O(n^1)$ 假设每个子问题的规模基本一样

$a = 2, b = 2, d = 1,b^d = 2$ ,所以 $T(n) = O(nlogn)$


例:LeetCode 236. 二叉树的最近公共祖先
LeetCode 题解 | 236. 二叉树的最近公共祖先(经典递归 C++)

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL)
            return NULL;

        // 可认为左右子树已经实现了函数的功能
        TreeNode* left =  lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        if(root == p || root == q) 
            return root;

        if(left == NULL)
            return right;
        if(right == NULL)
            return left;      
        if(left && right) // p和q在两侧
            return root;

        return NULL; // 必须有返回值
    }
};

$T(n) = 2T(n/2) + O(n^0)$ 假设每个子问题的规模基本一样,也就是说我们可以假设左右子树的结点数相同

$a = 2, b = 2, d = 0,b^d = 1$ ,所以 $T(n) = O(n)$


例:LeetCode 105. 从前序与中序遍历序列构造二叉树

LeetCode 题解 | 105. 从前序与中序遍历序列构造二叉树(递归 C++)


主定理证明

参考证明


Author: SHWEI
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint polocy. If reproduced, please indicate source SHWEI !
评论
 Previous
GitHub中Pull Request的具体过程详解 GitHub中Pull Request的具体过程详解
Pull Request 简单明了的解释“有一个仓库,叫Repo A。你如果要往里贡献代码,首先要Fork这个Repo,于是在你的Github账号下有了一个Repo A2,。然后你在这个A2下工作,Commit,push等。然后你希望原始仓
2020-07-24
Next 
卡特兰数(Catalan number)定义、证明及例题 卡特兰数(Catalan number)定义、证明及例题
写在前面:卡特兰数这东西感觉挺常用的,并且公式很简单,那就花一下午总结一下,学点皮毛吧(反正遇到我还是不会 ) [PDF] 大三上组合数学课堂讲义 卡特兰数定义 卡特兰数的性质记住前几项:$C_0$ =1,$C_1$ = 1,$C_2$ =
2019-10-21
  TOC