有人能帮我写一个时间复杂度为O(1)但不是Ω(1)的函数吗？反过来也一样。如果能解释一下就更好了。
一个Big O为O(1)但不是Ω(1)的函数
4
- rda3mon
3
2一个函数什么时候是O(1)但不是Ω(1)？考虑一下它们各自的含义。 - aaronasterling
由于O(1)是一个常数，因此不能存在一个被O(1)上界限制的函数。这是我的想法… - rda3mon
这与https://dev59.com/QXA75IYBdhLWcg3wlqSh有关。 - andand
1个回答
10
大O表示<=，而大Omega表示>=，因此一个满足O(1)但不满足Omega(1)的函数是f(n) = 1/n。反之，满足Omega(1)但不满足O(1)的函数是f(n) = n。
- Keith Randall
14
3@Keith：你如何构建一个需要少于一步的分数步骤算法？ - Michael Madsen
5你做不到。但那不是问题所在。 - Keith Randall
那么，这首先是一个有效的问题吗？ - rda3mon
4如果你只谈论函数，那么这个问题是完全有效的。但是，如果一个函数代表算法的运行时间，它必须至少为1。在任何情况下，相反的情况（Omega(1)但不是O(1)）也是完全有效的。 - Keith Randall
据我所知，量子计算算法可能比数据量更快地执行计算 - 在O(sqrt(n))时间内搜索n个元素。目前仍然是理论上的，因为这样的量子硬件尚未被创建，算法正在被制作中。（目前已经创建的绝热量子计算机只是可能类型之一）。 - Grzegorz Wierzowiecki
显示剩余9条评论
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接