应用Master定理求解递归方程

朱雀 2022-08-09 01:59 195阅读 0赞

## 什么是Master定理 ##

### 简介 ###

**Master定理**也叫**主定理**。它提供了一种通过渐近符号表示递推关系式的方法。应用**Master定理**可以很简便的求解递归方程。然而，**Master定理**也有其不适用的地方，下面会讲到。

### 定义 ###

假设有如下递归方程:

T(n)=aT(nb)\+f(n)

其中n为问题规模，a为递推的子问题数量且a≥1，nb为每个子问题的规模（假设每个子问题的规模基本一样）且b>1，f(n)为递推以外进行的计算工作。

设

g(n)=nlogbn

则

T(n)=⎧⎩⎨⎪⎪⎪⎪⎪⎪Θ(g(n)),Θ(f(n)),Θ(g(n)lgn),g(n)f(n)>lgnf(n)g(n)>lgnf(n)=g(n)

一句话概括就是谁大取谁，相等就乘lgn。

### 不适用范围 ###

如上定义所述，当g(n)f(n)<=lgn或f(n)g(n)<=lgn时，**Master定理**是无能为力的。因此，当遇到上面的情况时是不能使用**Master定理**的。

## 怎么使用 ##

在应用Master定理时只需自己在心中默默的问上自己几个问题，就可以计算出递归方程的渐进复杂度。下面咱们走上一遍：

1.  a是谁，b是谁，g(n)是多少，f(n)又是多少？
2.  g(n)大还是f(n)大还是一样大？
3.  如果g(n)大，那么g(n)f(n)>lgn？
4.  如果f(n)大，那么f(n)g(n)>lgn ?

既然知道了怎么用，那下面就来几个例题再近距离感受下**Master定理**的强大。

## 举几个栗子 ##

### 二分搜索 ###

二分搜索的递归方程如下：

T(n)=T(n2)\+Θ(1)

按照上面的步骤，走上一遍试一下：

在这里，  
1. a=1,b=2,f(n)=1,那么g(n)=nlogba=nlog21=1  
2. f(n)=g(n)  
3. 因此T(n)=Θ(g(n)lgn)=Θ(lgn)

怎么样，是不是很简单。再举几个不同的栗子接着感受下

### 二叉树遍历 ###

二叉树遍历的递归方程如下：

T(n)=2T(n2)\+Θ(1)

继续按照上面的步骤走：

1.  a=2,b=2,f(n)=1,因此,g(n)=n
2.  g(n)大
3.  g(n)f(n)=n>lgn
4.  因此T(n)=Θ(g(n))=Θ(n)

依然不费力气，下面再来一个

### 随便想的栗子一 ###

递归方程如下所示：

T(n)=2T(n4)\+Θ(nlgn)

按照上面的步骤走：

1.  a=2,b=4,f(n)=nlgn,则g(n)=nlog42<n
2.  f(n)大
3.  f(n)g(n)=nlgnnlog42>lgn
4.  因此T(n)=Θ(f(n))=Θ(nlgn)

### 随便想的栗子二 ###

递归方程如下：

T(n)=2T(n2)\+Θ(nlgn)

这次再按照上面的步骤走：

1.  a=2, b=2, f(n)=nlgn, 则g(n)=n
2.  f(n)更大
3.  f(n)g(n)=lgn≯lgn
4.  因此，这个递归方程不能够使用**Master定理**解决

通过上面的几个栗子应该能对**Master定理**感觉的差不多了吧？但其实，还是有点小小的问题的。

## 一点问题 ##

我这篇博客里写的**Master定理**实际上并不是很严谨，为了更加简便理解与使用对原来的**Master定理**添加了些自己的理解在里面，完整的**Master定理**的定义可以参考下面[维基百科][Link 1]的描述或者直接到《算法导论》中查看。

当然，我理解的版本的**Master**定理或许有误，欢迎批评指正。

[Link 1]: https://zh.wikipedia.org/wiki/%E4%B8%BB%E5%AE%9A%E7%90%86

发表评论取消回复

表情：

评论列表（有 0 条评论，195人围观）

还没有评论，来说两句吧...

相关阅读

相关角谷定理_递归（C语言）

谷定理。输入一个自然数，若为偶数，则把它除以 2，若为奇数，则把它乘以 3 加 1。经过如此有限次运算后，总可以得到自然数值 1。求经过多少次可得到自然数 1。 ...

电玩女神/ 2024年04月18日 15:24/ 0 赞/ 80 阅读

相关【Python解方程：用Python求解方程的方法及应用】

【Python解方程：用Python求解方程的方法及应用】 Python是一门功能强大的编程语言，它不仅可以进行数据分析、机器学习等各种应用，还可以用来解决数学问题。在数学

川长思鸟来/ 2024年03月26日 21:43/ 0 赞/ 72 阅读

相关不定方程求解

![watermark,type\_d3F5LXplbmhlaQ,shadow\_50,text\_Q1NETiBA6LaFMzM4,size\_20,color\_FFFFF

我会带着你远行/ 2023年09月29日 08:31/ 0 赞/ 35 阅读

相关递归求解迷宫问题

package com.yg.recursion;/ @author GeQiLin @date 2020/2/24 16:01 /

╰+哭是因爲堅強的太久メ/ 2023年07月08日 02:42/ 0 赞/ 27 阅读

相关记录 Master定理

算法设计关于递归方程T(n)=aT(n/b)+f(n)复杂度之通用解法算法设计教材中给出的Master定理可以解决该类方程的绝大多数情况，根据Master定理：o-渐进上界

骑猪看日落/ 2023年07月03日 06:07/ 0 赞/ 6 阅读

相关递归 & master公式（主方法）

递归重复子问题太多（时间容易超限）。 1. 截止条件 2. 候选人 2.1 筛选条件 master公式（主方法）用来利用分治策略来解决问

我会带着你远行/ 2023年05月28日 05:27/ 0 赞/ 18 阅读

相关【算法】递归求解整数划分

描述将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数

矫情吗；*/ 2022年08月26日 15:25/ 0 赞/ 220 阅读

相关应用Master定理求解递归方程

什么是Master定理简介 Master定理也叫主定理。它提供了一种通过渐近符号表示递推关系式的方法。应用Master定理可以很简便的求解递归方程。然而，Mast

朱雀/ 2022年08月09日 01:59/ 0 赞/ 196 阅读

相关 HNUCM-OJ 1401: 递归求解

[http://acm.hnucm.edu.cn/JudgeOnline/problem.php?id=1401][http_acm.hnucm.edu.cn_JudgeOnl

一时失言乱红尘/ 2022年01月14日 08:05/ 0 赞/ 298 阅读

相关递归式求解

1. 主定理 1.1 主定理介绍 ![1522393-20190619093933717-911651906.png][] 1.2 不能使用主定理的情况（

た入场券/ 2021年10月18日 07:50/ 0 赞/ 1087 阅读