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

Question

我的一个同事问我一个问题:集合o(1) ( little o notation ) 为空？

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

提醒，little-o 的定义 Cormen :

A function f(n) is said to be in o(g(n)) if for any positive constant c>0, there exists a constant n0 > 0 such that 0 <=f(n) < cg(n) , for all 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
For non zero g(x)

但是，更重要的是，候选集 f(x) 是什么？

有些人定义了它real functions ^[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 称为有效函数，并在 his explanation of big O,Omega and Theta (1976) 中使用 O(n^-1)

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

的条件

o(1)中没有复杂度函数T(n)的算法

虽然很少 o 符号是在实数上定义的，但我们的算法复杂度函数却不是。它们是在自然数 ^[3] 上定义的。你要么按照指示去做，要么不做。您不能执行指令的一半，或 e^-1 指令。这意味着，复杂函数集是 f:N->N。由于没有像“empty program”这样没有指令的东西(回想一下调用它本身的开销需要时间)，它甚至将这个范围缩小到 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) 好吧，对于一般情况，图像可以是一个非自然数，但我们在这里假设最坏情况的复杂性，尽管对于一般情况来说这个说法仍然成立，因为没有空程序。