问算法查询
EN

Stack Overflow用户

提问于 2012-02-19 23:03:51

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

如果我们知道一个问题的时间复杂度的下界是Ω(n^2)，我是否正确地认为不可能有一个最坏情况下的时间复杂度O(n log n)算法。

发布于 2012-02-20 08:08:11

如果一个问题的时间复杂度的下界是Ω(n^2)，那就意味着解决这个问题的算法必须占用至少 C*n^2时间。

另一方面，您有一个算法，它最多占用的 K*n*logn时间。

此算法不能运行比nlogn更长的时间。您需要的是至少运行n^2时间的算法。

因此，该算法不可能解决这个问题。你是对的。

票数 0

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

原文链接：

https://stackoverflow.com/questions/9354194

复制

相似问题

问算法查询EN