有没有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的增加而减少，估计不会改变。

好吧，我想了一下，也许有一个算法可以遵循这个一般形式:

你需要计算一个1000节点图的旅行商问题，但是，你也有一个你不能访问的节点列表。随着不可访问节点列表的增加，问题变得更容易解决。

如果解决方案存在，它可以在常数时间=立即准备和访问。例如，如果您知道排序查询是针对倒序的，则使用LIFO数据结构。然后，假设选择了适当的模型(LIFO)，数据就已经排序了。

O(1/n)并不小于O(1)这基本上意味着你拥有的数据越多，算法运行得越快。假设你得到一个数组，如果它的元素少于10^{One hundred.}，则总是填充到10^{One hundred.}元素，如果多于10^{One hundred.}，则什么也不做。这个当然不是O(1/n)，而是O(-n):)太糟糕了，O大符号不允许负数。

那么这个呢:

void FindRandomInList(list l)
{
while(1)
{
int rand = Random.next();
if (l.contains(rand))
return;
}
}

随着列表大小的增加，程序的预期运行时间会减少。

从我之前学习的大O符号来看，即使你需要1步(比如检查一个变量，做一个赋值)，那也是O(1)。

注意，O(1)和O(6)是一样的，因为“常数”并不重要。这就是为什么O(n)和O(3n)是一样的。

如果你需要1步，那就是O(1)。因为你的程序至少需要1步，所以算法的最小值是O(1)。除非我们不这样做，那么它是O(0)，对吧?如果我们做任何操作，那么它就是O(1)这是它能达到的最小值。

(如果我们选择不这样做，那么它可能成为一个禅宗或道的问题……在编程领域，O(1)仍然是最小值)。

或者这样怎么样:

程序员:老板，我找到了一个方法来做它在O(1)时间!< br > 老板:没必要这样做，我们今天早上破产了 程序员:哦，那么，它变成了O(0)。

你不能低于O(1)但是O(k) k小于N是可能的。我们称它们为次线性时间算法。在某些问题中，次线性时间算法只能给出特定问题的近似解。然而，有时，一个近似解就可以了，可能是因为数据集太大了，或者计算所有数据的计算成本太高了。

sharptooth是正确的，O(1)是可能的最佳性能。然而，这并不意味着一个快速的解决方案，只是一个固定时间的解决方案。

一个有趣的变体，也许是真正的建议，是随着人口的增长，哪些问题会得到更容易。我能想出一个虽然是做作的半开玩笑的答案:

一组中有两个人生日相同吗?当n超过365时，返回true。虽然小于365，这是O(nln n)。也许不是一个很好的答案，因为问题不会慢慢变得简单，而是变成O(1)对于n > 365。

随着人口增长，哪些问题会变得更容易?一个答案是像bittorrent这样的东西，下载速度是节点数量的逆函数。与汽车加载越多速度越慢相反，像bittorrent这样的文件共享网络连接的节点越多速度就越快。

如果根本不运行函数(NOOP)呢?或者使用固定值。这算吗?

这个问题并不像有些人认为的那样愚蠢。至少在理论上，当我们采用大O符号的数学定义时，诸如O(1/n)之类的东西是完全合理的:

< img src = " https://i.stack.imgur.com/9ii3q.png " alt = " / >

现在你可以很容易地用g(x)代替1/x…很明显，上面的定义仍然适用于一些f。

为了估计渐近运行时增长的目的，这是不太可行的……一个有意义的算法不能随着输入的增长而变得更快。当然，你可以构造一个任意的算法来实现这一点，例如下面这个:

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

显然，随着输入大小的增长，这个函数花费的时间会越来越少……至少直到硬件强制的某个限制(数字的精度，sleep可以等待的最小时间，处理参数的时间等):这个限制将是一个常数下界，因此实际上上面的函数仍然的运行时间为O(1)。

但在现实世界的算法中，当输入大小增加时，运行时间会减少(至少部分减少)。不过请注意，这些算法将在O(1)之下显示运行时行为。不过，它们还是很有趣的。例如，以非常简单的文本搜索算法霍斯普为例。在这里，期望运行时将随着搜索模式长度的增加而减少(但是增加草堆长度将再次增加运行时)。

如果不管输入数据如何，答案都是一样的，那么你就有一个O(0)算法。

或者换句话说-答案在提交输入数据之前就已经知道了 -函数可以优化出来-所以O(0)

我不懂数学，但这个概念似乎是寻找一个函数，需要更少的时间，你添加更多的输入?在这种情况下，怎么样:

def f( *args ):
if len(args)<1:
args[1] = 10

当添加可选的第二个参数时，此函数会更快，因为否则必须赋值它。我意识到这不是一个方程，但维基百科页面说大o通常也应用于计算系统。

O(1)仅仅表示“常数时间”。

当你给循环[1]添加一个早期退出时，你(在大O符号中)把一个O(1)算法变成了O(n)算法，但使它更快。

诀窍是在一般情况下常数时间算法是最好的，线性比指数更好，但对于少量的n，指数算法实际上可能更快。

1:假设这个例子的列表长度是静态的

不，这不可能:

随着n在1/n范围内趋于无穷，我们最终得到1/(无穷)，这实际上是0。

因此，问题的大-oh类将是O(0)和一个巨大的n，但更接近常数时间和一个低n。这是不明智的，因为唯一可以在比常数时间更快的时间内完成的事情是:

void nothing() {};

甚至这也是有争议的!

只要你执行了一个命令，你至少在O(1)，所以不，我们不能有一个O(1/n)的大哦类!

大o符号表示算法的最坏的情况，这与其典型的运行时不同。证明O(1/n)算法是O(1)算法很简单。根据定义，
O (1 / n)——> T (n) & lt; = 1 / n, n > = C > 0
O (1 / n)——> T (n) & lt; = 1 / C,因为1 / n & lt;所有n > = 1 / C = C
O(1/n)——> O(1)，因为大O表示法忽略常数(即C的值不重要)

我经常用O(1/n)来描述随着输入变大而变小的概率——例如，在log2(n)次投掷中，一枚均匀硬币背面朝上的概率是O(1/n)。

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

我看到一个算法的上限是O(1/n):

由于程序外部的原因(可能是硬件的原因，也可能是处理器中的其他核心的原因)，有大量的输入正在发生变化，你必须选择一个随机但有效的输入。

现在，如果它没有变化，你可以简单地列出一个项目列表，随机选择一个，然后得到O(1)次。然而，数据的动态性质使我们无法列出列表，您只能随机探测并测试探测的有效性。(请注意，从本质上讲，不能保证返回时答案仍然有效。这仍然是有用处的——比如游戏中的单位AI。它可以射击在扣动扳机时从视线中消失的目标。)

它的最差情况性能为无穷大，但平均情况性能随着数据空间的填满而下降。

是的。

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

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

inline void O0Algorithm() {}

这是一个简单的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)是可能的，因为它描述了函数的输出如何随着输入大小的增加而变化。如果我们使用函数1/n来描述函数执行的指令数，那么对于任何输入大小，函数都不需要接收0条指令。更确切地说，对于每一个输入大小，超过某个阈值n，所需的指令数以一个正常数乘以1/n为界。由于不存在1/n为0的实际数字，并且常数为正，因此没有理由限制函数接受0或更少的指令。

在数值分析中，近似算法在近似公差范围内应具有次常数的渐近复杂度。

class Function
{
public double[] ApproximateSolution(double tolerance)
{
// if this isn't sub-constant on the parameter, it's rather useless
}
}

有次线性算法。事实上，Bayer-Moore搜索算法就是一个很好的例子。

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

当然，有一些算法，比如Konrad定义的算法，至少在某种意义上看起来应该小于O(1)。

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

如果你想研究这些算法，你应该定义你自己的渐近测量，或者你自己的时间概念。例如，在上面的算法中，我可以允许使用一定次数的“自由”操作。在上面的算法中，如果我通过排除除睡眠以外的所有时间来定义t'，那么t'=1/n，即O(1/n)。也许有更好的例子，因为渐近行为是微不足道的。事实上，我相信有人能想出一些能给出重要结果的感官。

这里有另一种方法来证明它:为了拥有一个函数，你必须调用这个函数，并且你必须返回一个答案。这需要固定的时间。即使余下的处理过程对较大的输入花费更少的时间，打印出答案(我们可以假设是单个位)至少需要常数时间。

有可能构造一个O(1/n)的算法。一个例子是一个循环，迭代f(n)-n的某个倍数，其中f(n)是某个函数，其值保证大于n，当n趋于无穷时，f(n)-n的极限为零。对于所有n, f(n)的计算也需要是常数。我不知道f(n)会是什么样子，也不知道这样的算法会有什么应用，但在我看来，这样的函数可能存在，但结果算法除了证明O(1/n)算法的可能性之外没有任何目的。

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

其余的大多数答案都将大o解释为专门关于算法的运行时间。但是因为问题没有提到它，我认为值得一提的是大o在数值分析中的另一个应用，关于误差。

许多算法可以是O(h^p)或O(n^{-p})，这取决于你是在讨论步长(h)还是除法数(n)。例如，在欧拉方法中，你在已知y(0)和dy/dx (y的导数)的情况下寻找y(h)的估计值。h越接近0,y(h)的估计值就越准确。为了求任意x的y(x)取区间0到x，把它分成n段，在每一点上用欧拉方法，得到y(0)到y(x/n)再到y(2x/n)，以此类推。

欧拉方法是O(h)或O(1/n)算法，其中h通常被解释为步长n被解释为你划分一个区间的次数。

在实际数值分析应用中也可以有O(1/h)，因为浮点舍入误差。你的间隔越小，某些算法的实现就会抵消得越多，丢失的有效数字就越多，因此在算法中传播的错误也就越多。

对于欧拉方法，如果你使用浮点数，使用足够小的步长和消去，你把一个小数字加到一个大数字上，而不改变大数字。对于通过在两个非常接近的位置求值的函数中相互减去两个数字来计算导数的算法，用(y(x+h) - y(x) / h)近似y'(x)，在平滑函数中y(x+h)接近y(x)，导致大量抵消和较少有效数字的导数估计。这将反过来传播到任何你需要导数的算法(例如，一个边值问题)。

我猜小于O(1)是不可能的。算法所花费的任何时间都称为O(1)。但是对于O(1/n)下面的函数呢。(我知道这个解决方案中已经出现了许多变体，但我猜它们都有一些缺陷(不是主要的，它们很好地解释了这个概念)。这里有一个，只是为了方便讨论:

def 1_by_n(n, C = 10):   #n could be float. C could be any positive number
if n <= 0.0:           #If input is actually 0, infinite loop.
while True:
sleep(1)           #or pass
return               #This line is not needed and is unreachable
delta = 0.0001
itr = delta
while delta < C/n:
itr += delta

因此，随着n的增加，函数将花费越来越少的时间。此外，如果输入实际为0，则函数将永远返回。

有人可能会说，这将受到机器精度的限制。因此，由于c eit有一个上界，它是O(1)。但我们也可以绕过它，通过在字符串中输入n和C。加法和比较是对字符串进行的。用这个方法，我们可以把n减小到任意小。因此，即使忽略n = 0，函数的上限也是无界的。

我也相信我们不能说运行时间是O(1/n)。我们应该写成O(1 + 1/n)