问双输入运行时间复杂度
EN

Stack Overflow用户

提问于 2020-06-02 21:46:15

回答 1查看 868关注 0票数 0

假设您有一个算法，对于大小为n=1000的输入，在您的计算机上运行的时间正好是1秒。如果算法的时间复杂度为T(n)=Θ(2^n)，那么在大小为Θ的输入上运行该算法需要多长时间的最佳猜测是什么？

对于Θ(nlogn)来说，当输入加倍时，我知道它在2秒(Θ(n))和4秒(Θ(n^2))之间，但是有更精确的方法吗？

一般说来，如果是Θ( n ^2)，我可以从数学上推导出双n的时间复杂度为4秒，Θ(n)为2秒，Θ(n^3)为8秒。但上述问题使我感到困惑。

任何帮助都是非常感谢的。

回答已采纳

发布于 2020-06-03 21:48:52

由于第一个函数的运行时是O(2^n)，如果从n=1000转到n=2000，则运行时乘以.2^1000啊呀。

对于第二个问题，是的，时间乘以2 2log(2)。正如您所看到的，这个逻辑并不能推断到任何运行时，但在这种情况下，它可以工作。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/62161895

复制

相似问题

问双输入运行时间复杂度EN