从Ω符号的定义来看，这意味着2^(n) >= c * 2^(n + k)。取两边的lg并进行简化，我看到了n >= lg(c) * (n + k)。如果我选择c= 1，n0 = 1，k为负常量，那么我可以看到这是真的。我想知道这是不是一个正确的分析，如果我选择一个正的k，那么它就是错误的。谢谢你的帮助。
浏览 22提问于2019-03-01得票数 1
回答已采纳
1回答
例如..我需要帮助的问题是展示5n² - 6n = Θ(n²)。6k² >= 5n² - 6n5n² - 6n >= n²
....but我该怎么做?！我记得在入职时发生了类似于...我假设这些都是真的，现在为每个n插入(n+1) ...做..某物?在这一点上我迷
浏览 2提问于2012-09-20得票数 1
回答已采纳
1回答
我在考试中被问到了以下问题：我知道O(n)的时间复杂度取决于元素的数量，因此随着元素数量的增加，完成操作所需的时间也会增加根据这个逻辑，说a和c需要O(n)的时间复杂性是正确的吗？
浏览 2提问于2016-05-07得票数 0
回答已采纳
2回答
最大排列数
、、、
一些排序算法，如插入排序，对于n！的某个子集具有Θ(n)渐近运行时。N个元素的可能排列，这意味着对于这些排列，对于某个常数k，插入排序执行的比较次数是kn。对于给定的常数k，任何给定的比较排序可以在kn个比较中终止的排列的最大数目是多少？
浏览 0提问于2019-02-26得票数 0
所以我很确定它是O(n) (但它可能不是O(N))，但是如何用替换来解决它呢？
假设T(n) <= c* n，归纳步骤是什么？
浏览 0提问于2014-09-16得票数 6
回答已采纳
1回答
= 1: else:尝试的解决方案：T(n)= T(n-1) + 1 + c -- True for all n >0
= T(n-2) + 2 + 2C
= T(n-k</em
浏览 2提问于2016-03-30得票数 0
我运行了一个程序来找出n+1和2**ceil(log2(n+1))之间的差，其中n是2的幂。它一直呈指数级增长。所以从大O的定义来看，没有常数c‘使得-因此
(2^(2^ceil(log2(n)))) != O(
浏览 28提问于2017-01-24得票数 0
回答已采纳
2回答
这是一个循环for (int i =0; i < N; i++){ sum ++1b。)此外，当一个问题要求一个"theta界限“时，有人也能解释一下这是什么意思吗
浏览 2提问于2011-01-23得票数 2
1回答
我试图编写一些代码来预测在给定的n维数组上执行离散傅里叶变换所需的时间，但我很难理解n维FFT的计算复杂性。据我所知：
N*(k*M*log(M)) + M*(k*N*log(N</e
浏览 4提问于2012-09-03得票数 20
回答已采纳
4回答
如果一个函数体调用3个不同的函数，所有的顺序O(n)，我如何计算外部(包含)函数的顺序？是的，这是家庭作业，令人惊讶的是，我没有在教科书中找到相关的例子，也没有找到我们最近讲座的幻灯片。private void bigFunction(){ smallFunction2(); // O(n)} /
浏览 5提问于2014-01-24得票数 2
回答已采纳
1回答
自然数n的立方根定义为最大自然数m，使得m^3≤n。计算n的立方根的复杂性(n用二进制表示法表示)是(B)任何常数k>0的O(n^0.5)而不是O((log n)^k)
(C)对于某些常数k> 0，O((log)^k)，而对于任何常数m&g
浏览 2提问于2013-12-24得票数 3
回答已采纳
1回答
我必须找到满足以下条件的小于或等于n的偶数的数目。任何偶数都可以写成(2^p)*k，其中p，k是某个常数，并且给定n也是偶数，因此n=(2^q)*m。现在有多少偶数小于或等于n将满足p>q？
浏览 20提问于2020-06-07得票数 0
回答已采纳
1回答
T(n) = T(n-1)T(n) = T(n-1)..T(n) = T(n-k)T(n) = T(1)T(n) = O(1)
我不能完全确定这是否正确，但我不确定这是否如此容易。
浏览 0提问于2013-02-28得票数 1
回答已采纳
1回答
假设我们有一个函数f(n)= log，另一个函数g(N)=logn^2，问题是f(n)=O(g(n))还是f(n)=big_Theta(g(n))。由于log n^2 =2 log n，那么我的问题的另一种方式是，我们可以使用分数作为常数k吗？对于big_Theta选项，下限为k1=1/4，上限为<e
浏览 3提问于2015-10-22得票数 1
在大O符号中是O((log n)^k) = O(log n)，其中k是一些常量，对吗？那么当k>=0运行时，(log n)^k会发生什么呢？
浏览 0提问于2013-03-06得票数 0
回答已采纳
2回答
如何写出伪码的递推关系？
、、、、
if (f = l) then else return min(Foo(A,f,m), Foo(A请你带我找到解决办法好让我明白吗？我甚至不知道从哪里开始。
浏览 4提问于2016-09-24得票数 0
回答已采纳
1回答
f(n)∈O( g(n) )，g(N)∈Θ(f(N))g(n)∈Ω(f(N))，始终为真我的逻辑是因为g(n)∈Θ( f(n) )，g(n)和f(N<
浏览 0提问于2015-12-05得票数 0
1回答
求解多项式方程，求根(u*X^3-N*p*r*x^2-N*p^2+ K^2*u*X *K^2*p)，其中u和K是常数，N是常数数组，p，r是进化参数。基本上，对于每一代人口中的每一个个体，我需要做以下计算(长度(N)>>length(P))： for j = 1:length(N
浏览 3提问于2017-04-17得票数 2
回答已采纳
4回答
有人能解释一下这句话吗？评论说：
如果不考虑常数因素，就不能直接比较大O值。对于小列表(而且大多数列表都很小)，ArrayList的O(N)比LinkedList的O(1)更快。
浏览 0提问于2012-07-19得票数 5
回答已采纳
云服务器
ICP备案
云直播
对象存储
腾讯会议
腾讯云开发者
