o(1)中是否有任何函数？

Question

我的一位同事问了我一个问题:那套o(1)(小符号)是空的吗？

我的问题是:是o(1)空集吗？如果没有,是否有一个o(1)时间复杂的程序？

提醒,科尔曼对小o的定义:

一个函数f(n)被说成是o(g(n))如果任何利好不断c>0,存在常数n0 > 0,使得0 <=f(n) < cg(n)对所有n>= n0.

直观地说,如果f(n)是o(g(n))如果是O(g(n)),但这种结合不紧.

Answer 1

该集合o(1)不为空.

首先要记住的f(x)是,o(g(x))当且仅当

lim_x-> infinity {f(x)/ g(x)} = 0
对于非零g(x)

但是,更重要的是,候选人是f(x)什么？

有些人在所有真实函数 ^[1]上定义它,即f:R->RU{U}(对于某些函数值,U未定义).这意味着,我们可以使用任何真实到真实的功能,包括功能f(x)=1/x.我们还可以看到这g(x)=1是一个非零函数,事实上:

lim_x-> infinity {1/x/1} = 0

这意味着,o(1)包括函数f(x)=1/x,我们可以断定集合是空的.
Knuth还将该函数g(n) = n^-1称为有效函数,并O(n^-1)在他对大O,Omega和Theta的解释中使用(1976)

其他人,Cormen就是其中之一,将集合定义为f:N> N,其中N = {0,1,...},这也包括f(x)=0,它再次成为o(1)的条件.^[2]

没有与复杂功能无算法T(n)中o(1)

虽然在实数上定义了很少的符号,但算法的复杂性函数却没有.它们是在自然数上定义的^[3].你要么做指示,要么不做.你不能做一半的指令,或e ^-1指令.这意味着,复杂功能集是f:N->N.由于没有没有指令的" 空程序 "(回想一下调用它本身的开销需要时间),它甚至会将此范围缩小到f:N->N\{0}.

换句话说,对于算法的任何复杂度函数T(n),并且对于所有n>0,T(n)>0.

我们现在可以回到我们的公式:

lim_x-> infinity {T(x)/ 1}> = lim_x-> infinity {1/1} = 1> 0

这表明我们没有正面的自然函数o(1),我们可以得出结论,没有算法具有复杂性函数o(1).

脚注:
(1)如果你不确定它,请回忆泰勒系列,在某些时候我们停止添加无限系列,并提到它是O(x^n).我们在这个大O符号中"隐藏"的功能并不是自然数字.
(2)然而,如果我们将集合N + = {1,2,...}定义为正自然数的集合,并且将o(g(n))定义为正自然函数的子集,则o(1)是一个空集,其证明与没有算法具有这种复杂性的证明相同.
(3)嗯,对于普通情况,图像可以是非自然数,但我们假设最坏情况复杂,尽管声称仍然可以保持平均情况,因为没有空程序.