空算法的时间复杂度是否为O（0）？

Question

因此，给出以下html" target="_blank">程序：

该程序的时间复杂度是否为O（0）？换句话说，是0 O（0）吗？

我以为在一个单独的问题中回答这个问题将使这个问题更加清晰。

编辑：这里有很多好的答案！我们都同意0是O（1）。问题是，0 O（0）也是吗？

Answer 1

从维基百科：

用大O表示法描述功能通常仅提供功能增长率的上限。

根据此描述，由于空算法需要执行0次，因此其上限性能为O（0）。这意味着它也是O（1），碰巧是一个较大的上限。

编辑 ：

更正式地来自CLR（1ed，第26页）：

对于给定的函数 g （ n ），我们将 O （ g （ n ））表示为函数集

ø （ 克 （ Ñ ））= { ˚F （ Ñ ）：存在正的常数 Ç 和 Ñ 0，使得0≤F（N）≤ CG （ Ñ
）的所有 ñ ≥ Ñ 0 }

因此，无论输入如何，在0时间内执行的空算法的渐近时间性能都是 O （0）的成员。

编辑2 ：

我们都同意0是O（1）。问题是，0 O（0）也是吗？

根据定义，我同意。

此外，我认为这个问题的意义比许多答案表明的要重要得多。就其本身而言，空算法可能毫无意义。但是，无论何时指定非平凡算法，都可以将空算法视为位于指定算法的连续步骤之间以及算法步骤之前和之后。很高兴知道“虚无”不会影响算法的渐近时间性能。

编辑3 ：

亚当·克鲁姆提出以下主张：

对于任何函数 f （ x ）， f （ x ）都在O（ f （ x ））中。

证明：让 小号 是的一个子集 - [R 和 Ť 是的一个子集 - [R （非负实数），并让 ˚F （ X ）：

小号 - > Ť 和 Ç ≥1。然后0≤ ˚F （ X ）≤ ˚F （ X ），其通向0≤ ˚F （ X ）≤
CF （ X ）对于所有X∈
小号* 。因此 f （ x ）∈O（ f （ x ））。

具体地，如果 f （ x ）＝ 0，则 f （ x ）∈O（0）。