是否存在"负面"大O复杂性这样的事情？

Question

可能重复:
是否有任何O(1/n)算法？

这只是因为没有特别的原因突然出现在我脑海中,我想这是一个奇怪的问题.是否有任何已知的算法或问题实际上通过更大的输入更容易或更快地解决？我猜测,如果有,那就不会出现像突变或排序这样的事情,那就是决策问题.也许有一些问题,有大量的输入可以很容易地决定一些东西,但我无法想象.

如果没有负面复杂性这样的东西,是否有证据证明不存在？或者只是没有人找到它？

Answer 1

不,这是不可能的.由于Big-Oh被假设为算法执行的与其域大小相关的操作数的近似,因此将算法描述为使用负数操作是没有意义的.

维基百科文章的正式定义部分实际上定义了使用正实数的Big-Oh表示法.所以实际上甚至没有证据,因为Big-Oh的整个概念对于每个正式定义的负实数没有意义.

简短的回答:它不可能,因为定义是这样说的.

Answer 2

更新 只是为了清楚起见，我正在回答问题的这一部分：是否有任何已知的算法或问题实际上可以通过更大的输入更容易或更快地解决？

正如这里接受的答案中所指出的，没有算法可以在更大的输入下更快地工作。 有没有 O(1/n) 算法？ 即使像这样的算法sleep(1/n)也必须花时间读取其输入，因此其运行时间有下限。

特别是作者参考了比较简单的子串搜索算法：http :
//en.wikipedia.org/wiki/Horspool

PS但对此类算法使用术语“负复杂性”对我来说似乎不合理。