空算法的时间复杂度是O(0)?

从 Wikipedia :

根据这个描述,由于空算法需要0时间来执行,所以它的性能上限为O(0)。这意味着,它也是O(1),恰好是一个更大的上界。

编辑 :

对于给定函数 克 ( n O ( 克 ))函数集

( ( n )) = { ( n ):存在正常量 和 n ₀ 重心 ( )对所有人 }

因此,空算法的渐近时间性能,在0时间内执行,与输入无关,是 O (0).

编辑2 :

根据定义,我同意。

此外,我认为这个问题比许多答案所表明的更有意义。空算法本身可能毫无意义。然而,每当指定一个非平凡算法时,空算法可以被认为是位于被指定的算法的连续步骤之间以及在算法步骤之前和之后。很高兴知道“无”并不影响算法的渐近时间性能。

编辑3

Adam Crume 作出以下决定 claim :

对于任何函数 f ( ), f 十 )在O中( f 十 )).

S 是…的子集 R 和 T 是…的子集 R (非负实数)让 ( 十 ): -&燃气轮机; 和 c ≥ 1.然后是0≤ ( 十 ) ≤ f 十 )结果是0≤ f 十 ) ≤ 囊性纤维变性 ( 十 )对于所有x S . 因此 ( 十 十 )).

具体来说,如果 ( )=0,则 f )O(0)。

不管输入是什么,运行所需的时间都是相同的,因此定义为O(1)。

有几个答案说复杂性是O(1),因为时间是一个常数,并且时间是由某个系数和1的乘积所限定的。是的,时间是一个常数,它是有界的,但这并不意味着最好的答案是O(1)。

空算法在O(n^2)和O(n)中,在O(1)和O(0)中。我投O(0)的票。

对于空算法O(0),我有一个非常简单的参数:对于任何函数f(x),f(x)在O(f(x))中。简单地让f(x)=0,我们得到0(空算法的运行时)在O(0)中。

顺便说一句,我讨厌人们写f(x)=O(g(x)),当它应该是f(x)的时候∈ O(g(x))。

大O是渐近表示法。要使用大O,你需要一个 功能 -换句话说,表达式必须由n参数化,即使不使用n。说数字5是O(n)是没有意义的,常数函数f(n)=5就是O(n)。

所以,要用大O来分析时间复杂度,你需要一个n的函数。你的算法总是可以说是0步,但是如果没有一个变化的参数,谈论渐近行为是没有意义的。假设您的算法由n参数化。现在你才可以使用渐近符号。说它是O(n)是没有意义的 ²

一旦你确定了步数,这就是大O的定义:函数f(n)=0就是O(0)。

由于这是一个低级问题,它取决于计算模型。 在“理想主义”的假设下,你可能什么都不做。 但在Python中,您不能说 def f(x): ,但仅限于 def f(x): pass . 如果你假设每一条指令 pass c != 0 你只能这么说 f

值得注意的是,big O本身与算法没有任何关系。例如,你可以说sinx=x+O(x )在讨论泰勒展开式时。而且,O(1)并不意味着常数,它意味着由常数所限定。

到目前为止,所有的答案都在回答这个问题,就好像有对的和错的答案一样。但是没有。这个问题是个定义问题。通常在复杂性理论中,时间成本是一个整数——尽管这也只是一个定义。您可以自由地说,立即退出的空算法需要0个时间步或1个时间步。这是一个抽象的问题,因为时间复杂性是一个抽象的定义。在现实世界中,你甚至没有时间步,你有连续的物理时间;一个CPU可能有时钟周期,但并行计算机很容易有异步时钟,而且在任何情况下,时钟周期都非常小。

应该是O(1)。系数始终为1。

如果某物长得像5n,你不说O(5n),你说O(n)[换句话说,O(1n)]

同样,你应该说O(1),而不是O(其他常数)

O(0) . 即使是一台甲骨文机器或一台超级计算机也需要一次操作的时间。 solve(the_goldbach_conjecture)

所有的机器,无论是理论的还是实际的,有限的还是无限的,都能产生最小时间复杂度为的算法 O(1) .

但话说回来,这里的代码是 O(0) :

// Hello world!

:)

₁ g(n)等价于O(k) ₂ g(n))表示任何常数k _{1 2} 由此可知,O(1*1)等价于O(0*1),因此O(0)等价于O(1)。

例如,空算法与identity函数不同,后者的定义类似于“返回您的输入”。空算法更像一个空语句,或者两个语句之间发生的任何事情。它的定义是“对您的输入完全不做任何事情”,可能甚至没有简单输入的隐含开销。

讨论 O(0)的特例如下:

空算法在时间和空间上的复杂度均为O(0)。时间复杂度为O(0)的算法等价于空算法。

根据大O的正式定义:

设f(x)和g(x)是实数集合上定义的两个函数。然后,我们写道:

f(x) = O(g(x))

|f(x)| <= M * |g(x)| for every x > x0

在我看来,如果我们将g(x)=0(为了得到一个复杂度为O(0)的程序),我们必须:

|f(x)| <= 0

只有当f(x)=0时才是真的。

所以我想说,不仅空程序是O(0),而且它是唯一一个适用的。直观地说,这应该是正确的,因为O(1)包含了所有需要固定步数的算法,而不管它的任务大小,包括0。谈论O(0)基本上是无用的;它已经在O(1)中了。我怀疑这纯粹是出于我们使用的简单定义 O(1) ,也可能在那里 O(c) 或者类似的东西。

对于所有函数f,0=O(f),因为0<=|f |,所以也是O(0)。

除

假设有一个具有多种操作类型的数据结构,正在对其进行摊销分析。很可能有一种类型的行动总是可以得到资助的 完全地 使用先前操作中存放的“硬币”。

有一个简单的例子:Cormen,Leiserson,Rivest,Stein[CLRS09,17.2,p。457],以及 Wikipedia . 每次推一个物品,一枚硬币就放在物品上 摊余成本为2。当出现(多个)持久性有机污染物时,它们可以 完全地

请注意,MULTIPOP的摊余成本是一个常数(0) ... 此外,我们还可以对MULTIPOP操作不收费。打开 第一个板块,我们从板块中取出一美元的信贷,并用它来 支付POP操作的实际成本。为了打开第二个盘子,我们 操作,等等。因此,我们总是预先收取足够的费用 堆栈上有1美元的信用,堆栈上总是有一个 非负极板数,我们保证了 信用总是非负的。

因此,O(0)对于某些摊销业务来说是一个重要的“复杂性类别”。

O(1)表示算法的时间复杂度始终是常数。

假设我们有这个算法(在C中):

void doSomething(int[] n)
{
  int x = n[0]; // This line is accessing an array position, so it is time consuming.
  int y = n[1]; // Same here.
  return x + y;
}

如果我们算上2条最贵的线路,我们总共有2条。

2=O(1),因为:

如果我们有这个代码:

public void doNothing(){}

我想这只是一个约定,因为可以使用任何常量来表示O()中的函数。