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

Question

我的一个同事问我一个问题：集合o(1)（小符号）是空的吗？

我的问题是：是o(1)空集吗？如果没有，是否存在具有o(1)时间复杂度的程序？

提醒一下， Cormen对 little-o 的定义：

如果对于任何正常数，存在一个常数使得对所有人来说 ，f(n)则称函数在 中。o(g(n))c>0n0 > 00 <=f(n) < cg(n)n>= n0

直观地说，if f(n)is in o(g(n))if it is in 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) 好吧，对于平均情况，图像可以是一个非自然数，但我们在这里假设最坏情况的复杂性，尽管该声明仍然适用于平均情况，因为没有空程序。

Answer 2

函数 f(n)=0 在 o(1) 中，所以 o(1) 不为空。因为对于每个 c>0，f(n) < c * 1。

程序的时间复杂度是否可以为 o(1) 是一个意见（或定义）问题。如果您认为程序可以在没有基本操作的情况下存在，那么它的时间复杂度将在 o(1)。如果你认为一个程序没有基本操作就不能存在，那么无论输入如何，它总是至少需要 1 个时间单位，在 little-o 的定义中选择 c=0.5 可以证明它的时间复杂度是不是 o(1)。

Answer 3

由 的定义little o可知，要满足这个条件（即 o(1)），就必须有在任意短时间内完成的算法。
这与图灵机的定义相矛盾，图灵机需要“将无限带标记为正方形（有限大小）”。唯一的解决方案是执行 0 指令的空图灵程序。
但是，不能构建这样的程序，因为它需要机器，该机器以终止状态启动，因此不能执行任何其他程序并且不是图灵机。