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

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


当前回答

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

其他回答

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

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

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

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

inline void O0Algorithm() {}