有没有“消极”的大O复杂性[[副本]

维基百科的正式定义部分 article

简而言之:这是不可能的,因为定义是这样说的。

更新 我只想说清楚,我在回答这部分问题: 是否有任何已知的算法或问题,实际上更容易或更快地解决更大的投入?

正如这里公认的答案所指出的,有 不 Are there any O(1/n) algorithms? 甚至像这样的算法 sleep(1/n)

作者特别提到了相对简单的子串搜索算法:
http://en.wikipedia.org/wiki/Horspool

在一个以负时间执行的算法中思考,与思考时间倒流是一样的。

如果程序在上午10:30开始执行,并在上午10:00停止,而没有经过上午11:00,则它刚刚执行,时间=O(-1)。

=]

现在,数学部分:

如果你不能想出一个动作序列,在时间上向后执行(你永远不知道…哈哈) ,证明很简单:

正值时间=O(-1)表示:

正时间<=c*-1,对于任何c>0和n>不>0

考虑到这一点,结果是:

正时间<=负数,对于任何n>不>0

它只是证明了不可能有一个带O(-1)的算法。

不是真的。O(1)是你所能期望的最好的。

我能想到的最接近的是语言翻译,它使用目标语言中的大量短语数据集来匹配源语言中的较小片段。数据集越大,转换就越好(在一定程度上也越快)。但这还不是O(1)。

好吧,对于许多计算,比如“给定输入A返回f(A)”,你可以“缓存”计算结果(将它们存储在数组或映射中),如果其中一些值重复出现,这将使计算速度更快。

但我不认为这是“负复杂性”。在这种情况下,最快的性能可能算作O(1),最坏的性能是O(N),平均性能介于两者之间。

这在某种程度上适用于排序算法- 一些 其中有O(N)个最佳情况场景复杂度和O(N^2)个最坏情况复杂度,这取决于要排序的数据的状态。

我认为算法要有负的复杂度,就必须在被要求计算结果之前返回结果。也就是说,它应该连接到一个时间机器上,并且应该能够处理相应的数据 "grandfather paradox" .

与关于空算法的另一个问题一样,这个问题是一个定义问题,而不是什么是可能的或不可能的问题。当然可以考虑一个成本模型,对于这个模型,一个算法需要O(1/n)时间(这当然不是负数,而是随着输入的增加而减少。)算法可以做如下的事情 sleep(1/n) 正如另一个答案所暗示的那样。当n被送到无穷大时,成本模型确实崩溃了,但n从来没有被送到无穷大;不管怎样,每个成本模型最终都会崩溃。这么说 睡眠(1/n) 对于从1字节到1千兆字节的输入大小,花费O(1/n)时间可能是非常合理的。这对于任何时间复杂度公式都是一个非常广泛的适用范围。