这只是出于某种原因突然出现在我的脑海中，我想这是一个奇怪的问题。是否存在任何已知的算法或问题实际上可以 更轻松 或 更快速 地解决较大输入问题？我猜想，如果有的话，那不是突变或排序之类的东西，而是决策问题。也许存在一些问题，大量输入使决定某件事变得容易，但我无法想象。
如果没有负复杂性之类的东西，是否有证据证明不可能呢？还是只是没有人找到它？
不，那是不可能的。由于Big-Oh假定是算法执行的与其域大小相关的操作数的近似值，因此将算法描述为使用负数的操作就没有意义。
维基百科文章的正式定义部分实际上使用正实数来定义Big-Oh表示法。因此，实际上甚至没有证据，因为按照正式定义，Big-Oh的整个概念对负实数没有意义。
简短的回答：这是不可能的，因为定义如此。
