问理解何时使用θ来处理时间复杂性
EN

Stack Overflow用户

提问于 2019-01-15 14:52:17

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

我(相信)理解了大-O，大-Ω和大-Θ的定义，因为大-O是渐近上界，大-Ω是渐近下界，大-Θ是渐近紧界。但是，在某些情况下，例如在插入排序中，我一直对Θ的用法感到困惑：

据我所知，插入排序将：

这种困惑源于我对何时使用Big-Θ的理解。为此，我被引导相信，只有在Big-O和Big-Θ的值相同时，才能使用Big-Ω。如果是这样的话，为什么当Ω和O值不同时，插入排序被认为是O呢？

发布于 2019-01-20 05:16:04

基本上，只有在算法的运行时间上的上界和下界之间没有渐近间隙时，才能使用Big-Θ：

在您的示例中，插入排序最多需要O(n^2)时间(最坏的情况下)，而Ω(n)时间(最好的情况下)。因此，O(n^2)是算法的时间上界，Ω(n)是算法的下界。由于这两者并不相同，所以不能使用Big-Θ来描述插入排序算法的运行时间。

然而，考虑选择排序算法。它最坏的运行时间是O(n^2)，最好的运行时间是Ω(n^2).因此，由于上界和下界是相同的(渐近)，您可以说选择排序算法的运行时间是Θ(n^2)。

票数 2

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

原文链接：

https://stackoverflow.com/questions/54201310

复制

相似问题

问理解何时使用θ来处理时间复杂性EN