有没有时间复杂度为O(1)的函数？

Question

有没有时间复杂度为O(1)的函数？

algorithmbig-otime-complexitylittle-o

12

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

我的问题是：o(1)是一个空集合吗？如果不是，是否有一个时间复杂度为o(1)的程序？

提醒一下，Cormen对小o符号的定义如下：

如果存在正常数c>0，对于任意一个正整数n0 > 0，都有0 <=f(n) < cg(n)，则称函数f(n)是o(g(n))。

直观地说，如果f（n）在O（g（n））中，则它也在o（g（n））中，但这个上界并不紧密。

- amit

“小o”和Omega是一样的吗？ - Pacane

@Pacane 不是大O符号。在这里可以查看定义和维基百科链接。 - amit

3个回答

3

函数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)。

- Paul Hankin

1

从“小o”符号的定义可以得知，为了满足这个条件（即o(1)），必须存在一个能在任意短时间内完成的算法。这与图灵机的定义相矛盾，因为图灵机需要“无限的被分成有限大小方块”的纸带。唯一的解决办法就是执行0指令的空图灵程序。但是，这样的程序无法构建，因为它需要启动于终止状态，并且无法执行任何其他程序，也不是图灵机。

- Luka Rahne

1

我很喜欢你关于“没有图灵机可以具有O（1）的复杂度”的说法，但是当你将O（1）称为算法集合时，我无法点赞你的回答，因为它实际上是一组函数。你的回答可能非常适用于我的回答的第二部分，但是对于第一部分却失败并误导了读者，因为O（1）不是算法集合。 - amit

你是对的，我没有注意到函数和算法之间没有区别。在这种推理中也存在同样的漏洞。 - Luka Rahne

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

集合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、Omega和Theta（1976）的解释中使用了O(n^-1)。

其他人，如Cormen，将该集合定义为f:N->N，其中N={0,1,...}，这也包括f(x)=0，它再次满足o(1)的条件。^[2] 没有时间复杂度函数T(n)在o(1)中 虽然小o符号是针对实数定义的，但我们算法的复杂度函数不是。它们是在自然数上定义的^[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) 对于平均情况，图像可能是非自然数，但我们将在这里假设最坏情况的复杂度，尽管该声明仍然适用于平均情况，因为不存在空程序。