考虑递归关系T(N) = 2T(n-1/2) + n。根据主定理的第二种情况，我们会得到Θ(nlog(n))的时间复杂度，同时，使用替换方法(+归纳法)，我们也可以得到它在O(nlog(n))中，即我们可以证明c>1和n>1的T(N) <= cnlog(n为什么这是不同的，这有关系吗？谢谢!
浏览 22提问于2021-05-12得票数 0
回答已采纳
我有一个重复关系，如下所示：我使用递归树方法来解决这个问题。.+ log(n/2^(log N)*
在求解这个方程时，我得到了n(log n)^2的时间复杂度，但利用主定理，得到了n(log(log N))的时间复杂度，请帮助我找出我的错误。
浏览 2提问于2020-09-03得票数 0
1回答
我试图理解和实现大师定理，以找到递归关系的时间复杂性。 但是，我不能理解我们如何使用它来计算算法的时间复杂度。考虑这个寻找二叉树直径的算法 class Node int data; {of the given binary tree is: "
+
浏览 22提问于2019-03-06得票数 2
2回答
height and right heights */ }
用这种实现求树直径的时间复杂度是O(n^2)，其中n是树中的节点数？
浏览 1提问于2013-06-19得票数 1
有人能用反向替换解决上面提到的递归关系和渐近时间复杂度吗？我知道解决它的大师定理的方法，但我不知道如何使用反向替换来获得答案。
浏览 73提问于2020-02-03得票数 0
1回答
递归函数的时间复杂度
、、、、
根据Big-O表示法，我在确定这个递归函数的时间复杂度时遇到了一些麻烦。n); expRecursive(x, (n + 1)/2);
} ( expIterative方法的时间复杂度为O(n)) expRecursive() T( n ) = 2T(n/2) +n的递推关系是否成立？
浏览 21提问于2021-01-21得票数 0
1回答
这些循环关系的运行时间
、、、、
如何计算这些关系的紧束缚运行时？T(n)=T(n-3)+n^2
对于第一种方法，我使用了给出n^2但不正确的代换方法，第二种方法是用马斯特斯定理得到nlog^4(n)，这也是不对的彻底的解释是有帮助的。谢谢!
浏览 5提问于2015-05-17得票数 1
1回答
3递推T(n)与主定理
、、、、
假设我有下面的代码，我的任务是查找递归的T(n)及其最坏的运行时。如果n是列表的长度的值。在这种情况下，我们有3个递归，mystery(mylist[:len(mylist)-t-1])、mystery(mylist[t:len(mylist)- 1])和mystery(mylist[:len，我的观察是因为递归是在一起的，所以递归是：
T(n) = T(floor(2n/3)) + T(
浏览 6提问于2021-11-08得票数 1
1回答
时间复杂度变量
、、、、
时间复杂性可以用其他变量来表示，还是总是用n表示？
例如，与O(n^2)不同，我将时间复杂度表示为O(a^2)，因为代码的递归关系使用a作为主要变量。
浏览 1提问于2021-04-15得票数 0
3回答
这是我正在尝试分析的一个算法(见下文)。我不明白为什么当合并排序具有O(n logn)时，这会有O(n)时间复杂度，它们似乎都在做同样的事情。那么两者都有相同的j时间复杂度，如果你让j作为行，那么2^j X c(n/2^j) = cn，它们的运行时间都是log n，其中n是元素的数量。
浏览 1提问于2012-08-09得票数 1
回答已采纳
我对解决上面提到的问题感到很沮丧。我试着用大师的方法来解决这个问题，但我没有完成.我有一个递归算法，需要3log n次(三个二进制搜索)来识别四个子问题，每个子问题的大小为n/4，然后单独求解，直到n小于输入给定的常量。因此，我得到了这样的结果：
浏览 4提问于2015-03-02得票数 2
回答已采纳
4回答
空间复杂性与时间复杂性权衡
、、、、
我一直在研究一些排序算法，并在时间和空间复杂度之间遇到了一些逆关系。例如，像selection这样的算法采用O(n^2)，但由于可以在适当的地方执行，所以只需要常量空间。然而，像合并排序这样的算法具有O(nlogn)时间复杂度，但需要O(n)空间。
是否有一个定理或定律将时间和空间的复杂性相互权衡？这种现象是只存在于排序算法中，还是在其他问题上也存
浏览 0提问于2018-02-22得票数 1
回答已采纳
一段时间前，我学习了离散数学(在其中我学到了主定理，between /Omega/O)，我似乎忘记了O(logn)和O(2^n)之间的区别(不是在大Oh的理论意义上)。我通常理解合并和快速排序这样的算法是O(nlogn)，因为它们反复地将初始输入数组划分为子数组，直到每个子数组在递归回树之前大小为1，给出一个高度为logn +1的递归树。但是，如果使用n/b^x =1计算递归树的高度(当
浏览 4提问于2016-01-09得票数 11
回答已采纳
1回答
== 1 || n == 1) { }}Map<String, int> memo = {};
if (m == 0 || n =}
浏览 2提问于2021-05-05得票数 1
3回答
我对什么是解决时间复杂性感到困惑。我知道如何确定一个算法是O(1)还是O(n)等等。但是，对于运行时间，您总是手动求解吗?还是算法输出运行时间？我不知道O(1)的算法是做什么的？在练习中，我需要测量不同大小数组的时间复杂度。绘制运行时与输入大小的关系图。
浏览 0提问于2019-02-14得票数 1
回答已采纳
1回答
形成递归关系
、、
我有一个问题，形成递归关系和计算时间复杂性。
如果我们有一个递归关系T(n)=2T(n/2) +c，则表示当绘制递归树时，常工作量c被划分为2部分T(n/2) + T(n/2)。现在考虑阶乘的递推关系，即T(n)=n*T(n-1) +c。如果采用上述方法，则应将工作c分解为n个T(n-1)的实例，然后计算时间复杂度。但是，如果用这种方式计算，则会回答O
浏览 3提问于2016-11-12得票数 0
回答已采纳
1回答
需要分析递归函数的复杂性。功能如下。int j=0;j<n * n;j++){ } return hello(n-1);我感到困惑的一步是你好我不知道如何评估这种代码的复杂性。如果你一步一步地告诉这个问题的解决办法，我会非常感激的。提前谢谢。
浏览 2提问于2021-08-23得票数 1
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
云直播活动推荐
腾讯云开发者
