问大O与大Theta平等
EN

Stack Overflow用户

提问于 2017-08-15 20:16:59

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

例如，我被问到构建二进制堆的渐近复杂性(算法的类型是任意的)，如果我说算法是Θ(log(n))，那么说它是O(n)也是正确的吗？

回答已采纳

发布于 2017-08-15 20:23:43

只要您测量的是相同的量，任何Θ(log )都是O(n)。如果运行时是Θ(log )，那么它也是O(log )(这是Θ表示法定义的一部分)，任何O(log )也是O(n)。

您可能需要小心的情况是，如果这些是隐式测量不同的数量。例如，如果算法的最佳运行时是Θ(log )，则不一定认为该算法的最坏情况运行时是O(n)。

票数 1

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

原文链接：

https://stackoverflow.com/questions/45700865

复制

相似问题

问大O与大Theta平等EN