有没有O(1/n)种算法?

或者其他小于O(1)的数?

当前回答

这是一个简单的O(1/n)算法。它甚至做了一些有趣的事情!

function foo(list input) {
  int m;
  double output;

  m = (1/ input.size) * max_value;  
  output = 0;
  for (int i = 0; i < m; i++)
    output+= random(0,1);

  return output;
}

O(1/n) is possible as it describes how the output of a function changes given increasing size of input. If we are using the function 1/n to describe the number of instructions a function executes then there is no requirement that the function take zero instructions for any input size. Rather, it is that for every input size, n above some threshold, the number of instructions required is bounded above by a positive constant multiplied by 1/n. As there is no actual number for which 1/n is 0, and the constant is positive, then there is no reason why the function would constrained to take 0 or fewer instructions.

2009-09-15 22:43:43

其他回答

正如已经指出的，除了null函数可能的例外，不可能有O(1/n)个函数，因为所花费的时间必须接近0。

当然，有一些算法，比如康拉德定义的算法，它们至少在某种意义上应该小于O(1)

def get_faster(list):
    how_long = 1/len(list)
    sleep(how_long)

If you want to investigate these algorithms, you should either define your own asymptotic measurement, or your own notion of time. For example, in the above algorithm, I could allow the use of a number of "free" operations a set amount of times. In the above algorithm, if I define t' by excluding the time for everything but the sleep, then t'=1/n, which is O(1/n). There are probably better examples, as the asymptotic behavior is trivial. In fact, I am sure that someone out there can come up with senses that give non-trivial results.

2010-07-09 11:19:32

是的。

只有一种算法运行时为O(1/n)，即“空”算法。

对于O(1/n)的算法来说，这意味着它渐进地执行的步骤比由单个指令组成的算法少。如果对于所有n个> n0，它执行的步骤少于1步，则对于这n个，它必须完全不包含任何指令。由于检查' If n > n0'至少需要1条指令，因此对于所有n个，它必须不包含任何指令。

总结: 唯一的算法是O(1/n)是空算法，不包含任何指令。

2009-06-11 17:40:02

我不知道算法，但复杂度小于O(1)出现在随机算法中。实际上，o(1)(小o)小于o(1)这种复杂性通常出现在随机算法中。例如，如你所说，当某个事件的概率为1/n阶时，他们用o(1)表示。或者当他们想说某件事发生的概率很高时(例如1 - 1/n)，他们用1 - o(1)表示。

2016-04-24 19:15:15

没有比O(1)小的数大o符号表示算法的最大复杂度

如果一个算法的运行时间是n³+ n²+ n + 5那么它就是O(n³) 低次在这里根本不重要，因为n ->正无穷，n^2与n^3相比是无关的

同样地，当n -> Inf时，O(1/n)与O(1)相比是不相关的，因此3 + O(1/n)将与O(1)相同，从而使O(1)的计算复杂度最小

2009-05-28 00:08:51