有没有这样的事＆QUOT;负面＆QUOT;大O的复杂性？ [英] Is there such a thing as "negative" big-O complexity?
问题描述
可能重复：
是否有任何O（1 / N）的算法？
这只是突然出现在我的头，没有特别的原因，我想这是一个奇怪的问题。是否有任何已知的算法或问题，实际上得到的更容易或更快的解决有较大的输入？我猜测，如果有，它不会是喜欢的事情突变或排序，这将是对决策问题。也许有一些问题，其中有一吨的输入可以很容易地决定什么，但我无法想象。
This just popped in my head for no particular reason, and I suppose it's a strange question. Are there any known algorithms or problems which actually get easier or faster to solve with larger input? I'm guessing that if there are, it wouldn't be for things like mutations or sorting, it would be for decision problems. Perhaps there's some problem where having a ton of input makes it easy to decide something, but I can't imagine what.
如果没有这样的东西作为负面的复杂性，是否有证据表明不能有？或者是它只是没有找到它了吗？
If there is no such thing as negative complexity, is there a proof that there cannot be? Or is it just that no one has found it yet?
推荐答案
没有那是不可能的。因为大-喔被假设是操作的算法执行与其域的大小的数目的近似那就没有意义来描述的算法与使用操作的一个负数。
No that is not possible. Since Big-Oh is suppose to be an approximation of the number of operations an algorithm performs related to its domain size then it would not make sense to describe an algorithm as using a negative number of operations.
维基百科文章实际上定义了大哦符号使用正实数方面的正式定义部分。所以，这里居然竟然没有一个证明，因为大哦整个概念对按照正式定义的负实数没有意义。
The formal definition section of the wikipedia article actually defines the Big-Oh notation in terms of using positive real numbers. So there actually is not even a proof because the whole concept of Big-Oh has no meaning on the negative real numbers per the formal definition.
答案很简单：它不是可能的，因为其定义是这样说的
这篇关于有没有这样的事＆QUOT;负面＆QUOT;大O的复杂性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
