有没有O(1/n)种算法?
或者其他小于O(1)的数?
当前回答
我不知道算法，但复杂度小于O(1)出现在随机算法中。实际上，o(1)(小o)小于o(1)这种复杂性通常出现在随机算法中。例如，如你所说，当某个事件的概率为1/n阶时，他们用o(1)表示。或者当他们想说某件事发生的概率很高时(例如1 - 1/n)，他们用1 - o(1)表示。
其他回答
不，这不可能:
随着n在1/n范围内趋于无穷，我们最终得到1/(无穷)，这实际上是0。
因此，问题的大-oh类将是O(0)和一个巨大的n，但更接近常数时间和一个低n。这是不明智的，因为唯一可以在比常数时间更快的时间内完成的事情是:
Void nothing() {};
甚至这也是有争议的!
只要你执行了一个命令，你至少在O(1)，所以不，我们不能有一个O(1/n)的大哦类!
我经常用O(1/n)来描述随着输入变大而变小的概率——例如，在log2(n)次投掷中，一枚均匀硬币背面朝上的概率是O(1/n)。
我相信量子算法可以通过叠加“一次”进行多次计算……
我怀疑这是一个有用的答案。
这不可能。Big-O的定义是不大于不平等:
A(n) = O(B(n))
<=>
exists constants C and n0, C > 0, n0 > 0 such that
for all n > n0, A(n) <= C * B(n)
所以B(n)实际上是最大值，因此如果它随着n的增加而减少，估计不会改变。
如果根本不运行函数(NOOP)呢?或者使用固定值。这算吗?
