问Big theta，Big O，Omega函数运行时间
EN

Stack Overflow用户

提问于 2020-03-30 21:56:00

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

我目前正在研读算法的运行时间。我理解Big O，Theta和Omega的不同术语...下边、上边等边界...

然而，我有一些作业需要我列出Theta时间。log(n)+n*sqrt(n)就是一个例子

一般来说，人们可以只设置上限，但这不是Theta边界。你到底是如何找到一个函数的theta边界的？

到目前为止，我基本上只是应用了大O边界作为theta边界。然而，我担心这根本不正确。

发布于 2020-03-31 05:25:08

在您的示例中，这是Theta(n*sqrt(n))。

为什么？

因为lim [n->inf] n*sqrt(n) + logn / n*sqrt(n) > 0.，所以lim [n->inf] n*sqrt(n)+logn]/n*sqrt(n) < infinity

这意味着，n*sqrt(n)给了我们渐近的下界(欧米茄)和渐近的上界(O) -因此也是θ。

票数 1

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

原文链接：

https://stackoverflow.com/questions/60932132

复制

相似问题

问Big theta，Big O，Omega函数运行时间EN