关于复杂性的几个问题
1)将下列效率从最小到最大重新排序：
2^n, n!, n^5, 10000, nlog2(n)
我的Ans-> 10000 < nlog2(n) < n^5 < 2^n < n！
对吗？
2) algo的效率。是n^3，如果在这个algo中有一个步骤。需要1纳塞克。(10^-9秒)阿尔戈需要多长时间。处理1000大小的输入？
我不知道。是(1000)^3 * 10^-9吗？
回答 3
Stack Overflow用户
发布于 2009-07-27 14:58:11
第一个问题很好。问题二，我猜你的答案是他们在寻找什么，但是如果n^3是指O(n^3)，你实际上不能回答它(除非这是我不熟悉的“算法效率”的用法)。
大O复杂度给出了算法行为的一个渐近界.我们知道，对于“大”n，O( n ^3)比对n大小的输入执行算法所用的时间要大。注意两个注意事项--“大n”和“渐近界”。没有什么可以阻止大小为1000的输入占用2000大小输入的两倍长，只要存在一些m，使得对于所有n>m，n^3限制运行时。而且，没有什么可以阻止算法在每个输入上占用1纳秒，因为n^3仍然是运行时的一个界限--这是非常悲观的。
这就是为什么大O表示法在实际情况中的应用往往是有限的。它提供了一个公平的“最坏的情况”概述，但不涉及任何给定的使用场景。对于一个更实用的(但经常被忽略的)复杂性类集，google用于"Big“。
Stack Overflow用户
发布于 2009-07-27 14:46:00
两个答案都是正确的。
Stack Overflow用户
发布于 2009-07-27 14:46:19
1)是的，那是对的。
2)这也是正确的。量纲分析：(1000^3步)* 10^(-9)秒/步
https://stackoverflow.com/questions/1188546
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号