可能重复:
是否有任何O(1/n)算法？
您的代码是否可能比O(1)小O？
有人可以为我提供一个如何计算大theta的实时示例.
有点像平均情况,(最小 - 最大)/ 2？
我的意思是(最短时间 - 大O)/ 2
如果我错了请纠正我,谢谢
我有一个字符串数组,每个字符串都有不同的长度.例如:
s[0] = "sSWXk"
s[1] = "qCk"
s[2] = "sOQQXPbk"
.
.
.
s[x] = "KVfdQk";
我也得到了
n = s[0].length() + s[1].length() + ... + s[x].length()
我需要一个时间复杂度为O(n)的排序算法,用于按字典顺序对这些字符串进行排序,以便(例如)
a < ab < b < bbc < c < ca
有什么建议？时间复杂度是算法的基本要求.
晚上好,
我想帮助比较一个大O和Θ算法.
我可以理解如何比较两个大O,但是
我对如何比较big-O与Θ或big-O与Ω等有什么不妥.
我将在下面发布一些例子:
Θ(2ⁿ)vsΟ(2ⁿ)
Θ(n 0.6)
vsΘ (n logn)
O(n)vsΩ(n⋅logn)
我正在缓存函数f(1),f(2),...,f(1e7)的结果.缓存中的元素将随机读取.在C中,我将其存储在向量中,因为访问复杂度为O(1).在Perl中,我应该将缓存存储在向量还是哈希中？
我觉得将它存储在哈希中不会利用输入是连续整数的事实.但另一方面,我可能会过度思考这一点.
让 f(n)= ( (n^2+2n)/n + 1/1000*(n^(3/2)))*log(n)
此功能的时间复杂度可能都是 O(n²*log(n)) and O(n^(3/2)*log(n))
这怎么可能？我认为这里的主导术语是n² (*log(n)),因此它应该O(n²*log(n))只是大O符号和时间复杂性措施感觉如此模糊
鉴于两个字符串:
str1 = "abcdefacbccbagfacbacer"
str2 = "abc"
我要找到其中最长的子串str1由字符子集组成str2,在这种情况下它将是 - 7 (acbccba).什么是解决这个问题的方法,至少复杂.首先我想到了DP.但是,我认为DP确实不是必需的,因为我们必须搜索子字符串,而不是子序列.然后我虽然后缀树.但这需要额外的预处理时间.
最好的方法是什么？实际上,这个问题是否适用于后缀树或DP？
在大多数流行的语言中,比如C/C++/C#/ Erlang/Java,我们有线程/进程; GPGPU计算市场正在增长.如果算法需要N个与数据无关的步骤,那么我们得到的性能就不一样,因为算法需要所有步骤都相互跟随.所以我想知道大O符号在并发世界中是否有意义？如果它与分析算法性能无关？
您可以在分布式环境中拥有N个或更多处理器(未来的GPGPU /集群/ FPGA,您可以根据需要获得尽可能多的内核 - 并发世界,不限于并行内核的数量)
你能解释一下我如何能得到这个算法的最坏情况Big O. 我正在阅读我的教科书,我遇到了类似这样的算法,但仍然不理解它背后的逻辑.
int t=0;
for(int x=0;x<num.length;x++){
for(int y=0;y<num.length;y++){
for(int p=0;p<num.length;p++){
for(int w=0;w<num.length;w++){
if(num[p][w]>num[x][y])
{
t=num[x][y];
num[x][y]=num[p][w];
num[p][w]=t;
}
}
}
}
}
当n是数组大小时,在Ruby中插入数组的预期数量级是多少？
谢谢