问比较函数的big-O和big-Omega
EN

Stack Overflow用户

提问于 2016-02-01 11:27:38

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

我可以找到函数的big-O和big-Omega，但我很难检查某个函数是另一个函数的big-O还是big-Omega。例如：

n^(1/2)是n^(2/3)的big-O还是big-Omega

log(5n)是10log(n)的big-O还是big-Omega

除了使用图形计算器之外，我不确定如何比较它们。有没有人可以给我介绍一个资源，它提供了比较函数增长的技术？

发布于 2016-02-02 07:17:43

第一个是微不足道的，你只需要比较它们的能力，所以a = n^(1/2)，<=，b = n^(2/3)。因此，你的a在O(n^(2/3))中，模拟b在Omega(n^(1/2))中。

对于第二个，你需要对数规则，它给你

log(5n) = log(5) + log(n)

//Since log(5) is constant
log(n) < 10log(n) //wait, 10 also

==> asymptotic equally growing, both in Theta

作为一个检查工具，你可以看看Wolfram|Alpha。

当函数比较复杂时，你也可以用它们的商的极限来检验n到无穷远。例如，查看适用于n!和n^n的。

大多数常用函数的快速reference。

希望它能帮上忙！

票数 1

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

原文链接：

https://stackoverflow.com/questions/35122590

复制

相似问题

问比较函数的big-O和big-OmegaEN