求递归关系时间复杂度的主定理
（Master Theorem）是一种用于分析递归算法时间复杂度的方法。它适用于具有特定形式的递归关系式，即形如 T(n) = aT(n/b) + f(n) 的递归关系式，其中 a ≥ 1，b > 1 是常数，f(n) 是一个给定的函数。
主定理的三种情况如下：
情况一：如果 f(n) = O(n^c)，其中 c < log_b(a)，则递归关系的时间复杂度为 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^c)，其中 c > log_b(a)，且对于某个常数 ε > 0，存在一个常数 d < 1和足够大的 n0，使得对于所有的 n ≥ n0，有 af(n/b) ≤ df(n)，则递归关系的时间复杂度为 T(n) = Θ(f(n))。
根据递归关系的形式和给定的函数 f(n)，可以根据主定理的三种情况来确定递归算法的时间复杂度。
腾讯云相关产品和产品介绍链接地址：
- 腾讯云计算服务：https://cloud.tencent.com/product/cvm
- 腾讯云数据库：https://cloud.tencent.com/product/cdb
- 腾讯云服务器：https://cloud.tencent.com/product/cvm
- 腾讯云人工智能：https://cloud.tencent.com/product/ai
- 腾讯云物联网：https://cloud.tencent.com/product/iot
- 腾讯云移动开发：https://cloud.tencent.com/product/mobdev
- 腾讯云存储：https://cloud.tencent.com/product/cos
- 腾讯云区块链：https://cloud.tencent.com/product/baas
- 腾讯云元宇宙：https://cloud.tencent.com/product/vr
相关·内容
2回答
/* Function to get diameter of a binary tree */
int diameter(struct node * tree)
{
/* base case where tree is empty */
if (tree == 0)
return 0;
/* get the height of left and right sub-trees */
int lheight = height(tree->left);
int rheight = height(tree->right);
/* get the
浏览 1提问于2013-06-19得票数 1
3回答
这是我正在尝试分析的一个算法(见下文)。我不明白为什么当合并排序具有O(n logn)时，这会有O(n)时间复杂度，它们似乎都在做同样的事情。
那么两者都有相同的j时间复杂度，如果你让j作为行，那么2^j X c(n/2^j) = cn，它们的运行时间都是log n，其中n是元素的数量。
Algorithm: BinarySum(A, i, n)
Input: An array A and integers i and n.
Output: The sum of the n integers in A starting at index i.
if n = 1 then
return A[i]
浏览 1提问于2012-08-09得票数 1
回答已采纳
一段时间前，我学习了离散数学(在其中我学到了主定理，between /Omega/O)，我似乎忘记了O(logn)和O(2^n)之间的区别(不是在大Oh的理论意义上)。我通常理解合并和快速排序这样的算法是O(nlogn)，因为它们反复地将初始输入数组划分为子数组，直到每个子数组在递归回树之前大小为1，给出一个高度为logn +1的递归树。但是，如果使用n/b^x =1计算递归树的高度(当子问题的大小为1时，正如在答复中所说的那样)，似乎总是得到树的高度为log(n)。
如果你用递归来解决Fibonacci序列，我想你也会得到一棵大小为logn的树，但是由于某种原因，算法的大O是O(2^n)。我
浏览 4提问于2016-01-09得票数 11
回答已采纳
3回答
我有下面的“分而治之”算法A1。
A1将大小为n的问题划分为具有n/4大小的4个子问题。然后，对它们进行求解，并给出了12n时间的解决方案。
如何编写递归方程，给出算法的运行时。
浏览 5提问于2017-03-26得票数 0
1回答
根据我对主定理的理解，一个算法可以递归地定义为：
a T(n/b) + O(n^d)
其中a是子问题的数量，n/b是子问题的大小，O(n^d)是子问题的重组时间。计算主定理的时间复杂度如下：
T(n) = { O(n^d) if d > log base b of a
{
{ O(n^d log n) if d = log base b of a
{
{ O(n^ (log base b of a) ) if d < log base b of a
我
浏览 0提问于2013-05-17得票数 3
回答已采纳
提示破解Gayle Laakmann McDowell:的编码采访
实现一个函数来检查二叉树是否平衡。对于这个问题，定义了一个平衡树，使得任何节点的两个子树的高度不会有一个以上的差异。
(下面是实例实现)
问题：，你能帮我理解为什么作者说isBalanced的时间复杂性是O(n log n)吗？我在某种程度上理解了它，并且能够很好地记住它，但我不能像其他时间复杂性(如O(n^2) )那样概念化为什么会出现这种情况。
int getHeight(TreeNode root) {
if (root == null) { return -1; }
return Math.max(getHei
浏览 1提问于2019-09-23得票数 1
3回答
主定理假设T(1)为常数吗？假设我有一个算法，时间复杂度是: T(n) = 2T(n/2) + O(1)，T(1) = O(logn)，这个算法的时间复杂度是多少？
浏览 1提问于2016-01-31得票数 0
4回答
在递归算法情况下计算时间复杂度？
、、、、
在使用递归算法的情况下如何计算时间复杂度？
例如t(n) = t(3n/2) + 0(1) (堆排序)
浏览 0提问于2011-11-02得票数 1
回答已采纳
1回答
为了计数排序数组中出现的数字，我使用了两次二进制搜索
二元搜索的递推关系是T(N/2)+1，调用它两次，它是2T(N/2) +2，对吗？
但是用主定理，我得到的结果是O(n)，这是错误的
def NbOcc(T,v) :
bg=Bg(T,0,len(T)-1,v) // T(N/2) +1
bd=Bd(T,0,len(T)-1,v) // T(N/2) +1
if bg>bd :
return 0
else :
return bd-bg+1
浏览 5提问于2021-11-09得票数 0
回答已采纳
2回答
排序矩阵搜索主定理分析
、、、、
所以问题是要找出x是否在按行和按列升序的排序矩阵的一个元素中。
示例：
1 2 3
4 5 6
7 8 9
我感兴趣的是找到这个问题的分而治之解决方案的时间复杂度。我已经在谷歌上搜索过了，但我只找到了O(m+n)解决方案，也从这个中找到了。但是他说(评论答案) "T(R) = 3T(R/4)"，为什么f(R) =0？
问题是，使用主定理的分而治之的解决方案的复杂性是什么？在T(R) = 3T(R/4) + f(R)中，f(R)应该是什么？
如果有帮助，这是我的分而治之的解决方案：
bool find_x_in_matrix(int x, int mat[3][3], int t
浏览 2提问于2013-02-12得票数 0
回答已采纳
public static long pow_2(long x, int n) {
if (n == 0)
return 1;
if (n == 1)
return x;
if (n % 2 == 0) {
return pow_2( x, n / 2 ) * pow_2( x, n / 2 );
}
else {
return pow_2(x * x, n / 2) * x;
}
}
空间复杂度不是OLog(n)吗，因为您在每次调用时都会对堆栈主机进行n/2次调用？
因
浏览 3提问于2018-09-15得票数 0
1回答
所以我在为算法考试做准备，我不知道如何解决这个递归的T(n) = T(6n/5) + 1，因为b = 5/6 < 1和主定理不能应用。我希望有人能给我一个如何解决这个问题的提示。:)
浏览 1提问于2018-05-13得票数 0
回答已采纳
你能告诉我代码的时间复杂度吗，我正在使用分而治之的技术？
<code>A0</code>
浏览 14提问于2019-12-02得票数 0
2回答
谁能解释一下以下算法的O(N)时间复杂度：
int count = 0;
for (int i = N; i > 0; i /= 2) {
for (int j = 0; j < i; j++) {
count += 1;
}
}
浏览 0提问于2018-10-31得票数 0
用主定理方法.Solving递推T(n) = T(n / 2) - T(n / 6) + O(lg )？
浏览 0提问于2020-04-11得票数 2
5回答
最近我一直在研究递归，怎么写，怎么分析，等等。有一段时间我一直认为递归和递归是一回事，但是最近作业和测验中的一些问题让我觉得有一些细微的差别，即“递归”是描述递归程序或函数的方法。
直到最近，我才意识到有一种叫做“主定理”的东西，用来写问题或程序的“递归”。我一直在看维基百科的网页，但是，和往常一样，事情的措辞方式让我不太明白它在说什么。我用例子学得更好。
因此，有几个问题:让我们假设您被赋予了这样的重复：
r(n) = 2*r(n-2) + r(n-1)；
r(1) = r(2) =1
实际上，这是主定理的形式吗？如果是的话，用言语来说，它是怎么说的？如果你试图写一个小程序或基于这种递归
浏览 15提问于2008-10-20得票数 6
回答已采纳
1回答
这种重复的时间复杂性？
、、、
我试图用主定理来计算这个循环的运行时复杂性。我对此有点迷茫，所以根据主定理。
T(N)=aT(n/b)+f(N)
我插入这个值
有多少递归(拆分)函数？
A=1
相对子问题大小。投入的减少率是多少？
B=L，因为子问题是独立的列表
运行时完成的工作以外的递归？
f(n) =n，例如，可能没有列表，只有整数
主定理的哪一种情况适用于此？
/*
341. Flatten Nested List Iterator on leetcode
Given a nested list of integers, implement an iterator to flatten it.
Each
浏览 2提问于2020-04-28得票数 0
1回答
首先，让我说我知道主定理的性质，所以问题不在这里。
我需要知道如何使用现有的算法来确定主定理的值。
所以，我需要T(n)=a*T(n/b) + f(n)。
我知道a是递归调用的数量。
我知道b是问题的大小。
但我不知道如何确定什么是f(n)
我举了个例子
这里我们有a=2；b=2 f(n) =n
a=2，因为我们有2倍的合并函数调用b=2，因为j=(k+i)/2
但我不明白我们怎么得到f(n)=n
mergeSort(T，i，k)
要求T阵列
i，k整数使得Tm<=i<=k<=TM与Tm和TM的界为T
确保T在i和k之间排序
`if (k>i) then
j=(
浏览 5提问于2017-10-24得票数 2
回答已采纳
这是我的递归函数：
function abc(n):
if n == 0
return xyz(n)
for i = 1 to n
print(xyz(n))
return abc(n/2) + abc(n/2)
而xyz()是ϴ(n^3)。主定理在这里有效吗？如果，是的，我该怎么写？
浏览 0提问于2017-04-20得票数 1
回答已采纳
2回答
递归函数的渐近复杂性是如何导出的
、、、、
我在网站上还没有找到这方面的一般答案
例如
如果我有一些算法，比如说二进制搜索，我如何推导(数学上显示)它的复杂性是O(log(n))。
但是更广泛地说，，我如何推导出任何递归算法的渐近复杂性？
浏览 2提问于2017-08-10得票数 2
回答已采纳
2回答
主定理与递归
、、、、
我想知道如何解决这个代码的主定理：
unsigned long fac (unsigned long n ) {
if (n == 1 )
return 1;
else
return fact(n-1)*n;
}
因此，基于这样的事实，我只有1次调用它自己，除了这个函数调用，没有其他的，所以O(n) =1。现在我在为我的b而奋斗。通常一般的公式是：
T(n) = a*T(n/2) + f(n)
在这种情况下，我没有划分主要的问题。这个新问题只能解决n-1问题.现在b是什么？，因为我的重复会是：
T(n) = 1*T(n-1) + O(1)
既然我
浏览 4提问于2017-05-20得票数 1
回答已采纳
1回答
我知道解决方案是绿色的，但我不知道如何计算它。
如果有人能解释我，或者只给我一个我能理解的链接，我将不胜感激。
谢谢。
浏览 4提问于2016-03-08得票数 0
回答已采纳
1回答
我设计了一个算法，将10的幂转换为二进制，假设n是2的幂。我使用高斯方法来利用这个很好的方法的快速运行时间。为此，我将n除以2，并将其发送到Gauess方法，如下所示：
changetoBinary(n)
if n=1
return binary of 10 which is 1010
else
return gauess(n/2,n/2)
很明显，猜测方法将首先分裂，然后征服，然后合并。最后，我们将数字更改为二进制。现在我的问题是关于算法的运行时间:我的理解是，由于猜测运行时间是θ(n^log3(Base2))，我们可以说这个算法的运行时间也是相同的，因为大多数工作都是由Gue
浏览 0提问于2014-02-21得票数 1
1回答
使用分治的数组的第二大元素
、、、、
我编写这个函数是为了找到数组中第二大元素，但我对它的时间复杂性有一些疑问。如果条件有θ(1)还是增加了递归调用的时间复杂度？
从实验的角度看，它不应大于最大的最大元素，具有分而治之的策略时间复杂度。
int secondmax(int arr[], int first , int last){
if(first+1==last) return arr[first];
int mid= first +(last-first)/2;
int left = secondmax(arr, first, mid);
int right = secondmax(arr, mid,
浏览 2提问于2019-06-22得票数 0
回答已采纳
1回答
这些循环关系的运行时间
、、、、
如何计算这些关系的紧束缚运行时？
T(n)=T(n-3)+n^2
T(n) = 4T(n/4)+log^3(n)
对于第一种方法，我使用了给出n^2但不正确的代换方法，第二种方法是用马斯特斯定理得到nlog^4(n)，这也是不对的。彻底的解释是有帮助的。谢谢!
浏览 5提问于2015-05-17得票数 1
1回答
我开始了解到，在随机快速排序的情况下，如果我们以这样的方式选择pivot，它至少会给出25%-75%的比例分割，那么运行时间是O(n log n)。现在我也知道我们可以用大师定理来证明这一点。
但我的问题是，如果我们在每个步骤中将数组分成25%-75%，那么我将如何定义我的T(n)，以及我如何证明O(n log n)中的运行时分析
浏览 0提问于2013-07-23得票数 0
回答已采纳
主定理是什么？二元搜索的时间复杂度是如何用这个定理得出的？我想知道这个话题的确切解释。提前谢谢你！
浏览 1提问于2020-04-10得票数 0
回答已采纳
1回答
我很难理解递归函数的时间和空间复杂性：
考虑：
def power(a, n):
if n==0:
return 1
else:
return a*power(a, n-1)
当发现时间复杂性时:我认为T(n) = c + T(n-1)，其中c是乘法的常数成本。
这可能导致: c*n成本，即线性成本O(n)。但递归的成本通常是指数级的。
此外，考虑到这一职能：
def power(a,n):
if n==0:
return 1
if n%2 ==0:
return power(a*a, n//2)
浏览 1提问于2018-02-13得票数 2
回答已采纳
1回答
我得到了以下算法：
Supersort(A, i, j):
if(j = i): return
if(j = i + 1):
if(A[i] > A[j]):
swap(A[i], A[j])
else:
k = floor of ( (j-i+1)/3 )
Supersort(A, i, j-k) // sort first two thirds
Supersort(A, i+k, j) // sort last two thirds
Supersort(A, i, j-k) // sort
浏览 3提问于2020-09-11得票数 1
回答已采纳
我特别在考虑QuickSort :每个子问题的大小大约是主问题的一半--是否是子问题，包括划分主问题然后重新组合解决的子问题的结果的开销，往往在主问题的一半时间内得到解决？ 我知道解子问题是并行的，这也是加速算法的一种方式，但QuickSort的大部分讨论都没有提到并行性。
浏览 48提问于2020-03-28得票数 0
3回答
我尝试了许多小时，我一直到达log(logn) (其中log是基2)，但这不符合马斯特斯定理，后者认为它只是log(n)。
浏览 6提问于2014-02-14得票数 3
回答已采纳
如何使用数学或大O表示法计算数据代数中使用的代数操作的时间复杂度。我将用书中的例子来解释我的问题。考虑一下书中给出的例子。B
在上面的例子中，我想计算转置和合成操作的时间复杂度。
如果可能的话，我还想找出其他代数数据操作的时间复杂度。如果你需要更多的解释，请告诉我。
@wesholler我编辑了我的问题以理解您的解释。下面是一个真实的例子，假设我们想要计算下面使用的操作的时间复杂度。
假设我有如下的数据操作代数
你能描述一下我们如何计算上面例子中的时间复杂度吗？最好是在大O区？
谢谢
浏览 0提问于2015-10-06得票数 0
1回答
最近我遇到了一个问题，其中渐近复杂性被问到- T(n, n) where
T(x, c) = Θ(x) for c ≤ 2,
T(c, y) = Θ(y) for c ≤ 2, and
T(x, y) = Θ(x + y) + T(x/2, y/2). 提出的解决方案是 We may then begin to replace T(x/2, y/2) with the recursive formula containing it:
x + y x + y x + y
T(x, y) = c (x + y) + c(x+y)/4 + c(x+y)/8 ...
This geometric s
浏览 15提问于2020-04-16得票数 0
根据主定理，这个递归是θ(n^2)，但是如果我们用树递归解决这个问题，那么解决方案是θ(n^2*logn)。我做错了什么吗？
浏览 258提问于2021-02-01得票数 2
回答已采纳
3回答
如何找到这种复杂性？
、、、
如果我有一个形式的函数，
int foo ( int n )
{
if ( n == 0 )
return 0;
else
return n + foo ( n-1)
}
使用big-O调用foo(foo(n))的运行时间是多少。
递归关系是f(n) = f(n-1) + n，f(0) =0，因此复杂度是大O(n^2)。但如何做到以上几点呢？
浏览 1提问于2014-09-15得票数 2
1回答
尽管我之前在stackoverflow上读了一些问题，看了一些视频，包括this one，但时间和空间的复杂性让我摸不着头脑。我需要找到这个算法的时间和空间复杂度。 public static int aPowB(int a, int b){
if(b == 0){
return 1;
}
int halfResult = aPowB(a, b/2);
if(b%2 == 0){
return halfResult * halfResult;
}
r
浏览 12提问于2020-11-01得票数 1
1回答
我已经为理解主定理而挣扎了一段时间。我发现的大部分信息似乎都假设我了解某些词汇。所以有个很长的问题..。
考虑以下例子：
const items = [1, 2, 3, 4, 5];
// O(1) Constant Time
const getByIdx = idx => items[idx];
}
// O(n) Linear Time
const findItem = val => {
for (let i = 0; i < items.length; i++)
if (items[i] === val) {
return items[i];
浏览 2提问于2018-06-19得票数 0
回答已采纳
1回答
3递推T(n)与主定理
、、、、
假设我有下面的代码，我的任务是查找递归的T(n)及其最坏的运行时。如果n是列表的长度的值。
在这种情况下，我们有3个递归，mystery(mylist[:len(mylist)-t-1])、mystery(mylist[t:len(mylist)- 1])和mystery(mylist[:len(mylist)-t-1])。
def mystery(mylist):
if len(L) <= 1:
return
if len(mylist) >= 3:
t = len(mylist) // 3
mystery(mylist[:l
浏览 6提问于2021-11-08得票数 1
1回答
我对算法非常陌生，我遇到了一个我不知道如何应用主定理的问题：
我们有一个算法A，它通过创建三个子问题来解决P，每个子问题都是2n/3大小的，递归地解决每个子问题，然后在O(nlogn)时间组合求解。这个算法会比O(n)有更好的运行时间吗？证明你的答案。
我在这里知道的是a=3，b=3/2，但是我如何处理O(nlogn)
浏览 1提问于2018-11-10得票数 0
T(n)= T(\sqrt{n})+logn
我在使用主定理解决这个递归问题时遇到了问题，如果我应用替换，事情会变得混乱。请建议一些程序来解决这类方程。
浏览 3提问于2020-07-08得票数 0
2回答
算法:主定理
、、
主定理可以用来解决象T(n)= aT(n/b)+f(n)这样的递推关系。
那么，如果f(n)=O(n)或f(n)=cn都是相同的值呢？我也可以用f(n)=cn的主定理吗？
浏览 4提问于2016-05-18得票数 3
回答已采纳
3回答
写一个程序，它接受一个整数，并打印出所有乘以等于原始数字的较小整数的方法，而不重复使用多组因子。换句话说，如果您的输出包含4* 3，则不应再次打印3*4，因为这将是一个重复的集合。请注意，这不仅仅是要求素数分解。此外，您可以假设输入整数的大小是合理的；正确性比效率更重要。PrintFactors( 12 ) 12*1 6*2 4*3 3*2*2
public void printFactors(int number) {
printFactors("", number, number);
}
public void printFactors(String expres
浏览 0提问于2016-08-15得票数 6
1回答
我需要帮助找到递归算法的复杂性；我知道为了解决这个问题，我必须找到线性递归，然后应用主定理。据我所知，如果只考虑一个参数，就可以很容易地找到递归；
在这种情况下，有两个参数(i，j)。考虑以下调用的函数(A,1，n)：
integer stuff(integer [] A, integer i, integer j){
if i ≥ j then return i – j
integer h ← 0
for integer k ← 1 to floor((j – i + 1)/3) do {
浏览 0提问于2019-07-08得票数 1
回答已采纳
我试图将主定理应用于这类循环：
T(n) = T(n/2) + 2^n
然而，f(n) = 2^n似乎不适合主定理中描述的三种情形中的任何一种，它们似乎都有基n而不是基2，我如何解决这类重复问题，谁能帮上忙呢？谢谢。
浏览 4提问于2014-09-26得票数 2
回答已采纳
我正在阅读“算法入门”一书，我有一个问题，即导出T(n)的下界和上界，以便进行下列重复：
T(n) = 36T(n/6) + 2n
它的说法是: T(n)是n <= 2的常数，有人能向我解释最后一句吗，这到底是什么意思？
assume that: T(n) is constant for n <= 2
浏览 0提问于2018-02-13得票数 1
回答已采纳
1回答
你好，我一直在练习算法和数据结构，我解决了这一powerset函数，但它看起来我的解决方案太慢了。以下是代码：
def subsets(array):
set = [array]
n = len(array)
for i in range(n):
tmp_subsets = subsets(array[:i] + array[i+1:])
for subset in tmp_subsets:
if subset not in set:
set.append(subset)
r
浏览 1提问于2019-05-01得票数 2
回答已采纳
我正在检查GeekforGeeks <code>C0</code>中的“到达终点的最小跳跃数”问题。我对这里提到的时间复杂度感到困惑，它是O(n^n)。
<code>A1</code>
如果我看到上面的代码块，minJumps(arr，i，h)递归调用是从i=l+1调用的，所以在每个递归步骤中，l(开始位置)递增1。时间复杂度应该计算如下。
<code>A2</code>
我不明白为什么时间复杂度是O(n^n)。在其他几个地方，我也看到这个递归解决方案的时间复杂度被提到为O(n^n)，没有适当的解释。请帮我做一个简单的解释
浏览 14提问于2021-06-15得票数 3
回答已采纳
有一个众所周知的动态规划问题，叫做“金矿”。你有一个n×n网格，每个单元格都包含一定价值的硬币。您从左下角开始，只能向右、向上或对角向上和向右移动。你的算法的目标是确定通过矿山的路径，最大限度地利用你收集的黄金数量。
一个示例解决方案：http://www.ideserve.co.in/learn/gold-mine-problem
用O(n)空间或更少的O(N)空间来解决这个问题，同时仍然使用O(n^2)时间，有可能解决这个问题吗？
我的第一个怀疑是，你可以递归地将网格划分成象限，在每个象限中找到最佳路径，然后以某种方式将最终的结果合并，从而获得整个过程中的最佳路径。仅使用O(n)空间，您可
浏览 0提问于2016-10-07得票数 2
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频活动推荐
腾讯云开发者
