最坏情况下复杂度与输入大小成反比的算法

Question

可能重复：
有O（1/n）算法吗？

任何算法的复杂度都会随着输入大小的增加而降低？

我说的是最坏情况下的表现。

一般来说，我们知道数学图的大小会随着输入大小而减小，但我们有任何有意义的算法来匹配这些图吗？

Answer 1

这个怎么样？

 Mystery(array[1..n])
 1. x := fn(0)
 2. for i = 1 to floor(1,000,000 / n) do
 3.    x = fn(x)
 4. return x

出于显而易见的原因，所有这些算法都是恒定时间的，渐近地说。

编辑：

实际上，这是渐近的O（logn），如果整数除法是对数的，我相信它是对数的。http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations因此，我的答案是实际上没有任何O（1/n）算法。O（1）是最小的复杂度类……除非有一种方法可以使算法在不计算输入大小的情况下知道其倒数！

第2版：

我只是想把1000000/n作为输入传递给函数。。。但这并不是真正的解决方案，因为算法无法判断是否违反了该条件，而且调用者无论如何都需要计算它。请注意，如果你将算术运算视为恒定时间，那么很多讨论都不是特别相关，因为我很确定它们是在具有固定大小的内在类型和在定义的寄存器大小上操作的指令集的计算机上进行的。

Answer 2

类似的东西

f(Collection c, query q):
  if q in c:
    do something fast!
  else:
    compute Ackermann function!
f*(Array a, int i):
  if a[i] == i: //Or some other condition that takes constant time to verify,
                //assume i is within bounds
    do something fast!
  else:
    compute Ackermann function!

当然，它的性能取决于a[i]=i的概率。我还没有做任何彻底的分析，但我想，要计算这个概率，你需要对数组的性质和f*是如何被调用的进行某种形式的假设。

这很有趣，但我无法想象我会遇到这种情况。

编辑：最初的答案是f，但为了适应哈罗德的评论，将其改为f*。在那之后，我休整了我的案子，就潜伏起来。