algorithm - 空算法的时间复杂度是O(0)吗？

Question

所以给定以下程序:

---

这个程序的时间复杂度是O(0)吗？换句话说，是0 O(0)吗？

我认为在一个单独的问题中回答这个问题会阐明 this question .

编辑:这里有很多好的答案!我们都同意 0 是 O(1)。问题是，0 O(0) 也是吗？

Answer 1

来自 Wikipedia :

A description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function.

从这个描述来看，由于空算法需要 0 时间来执行，因此它具有 O(0) 的上限性能。这意味着，它也是 O(1)，恰好是一个更大的上限。

编辑:

更正式地来自 CLR(第 1 版，第 26 页):

For a given function g(n), we denote O(g(n)) the set of functions

O(g(n)) = { f(n): there exist positive constants c and n₀ such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n₀ }

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

编辑 2:

We all agree that 0 is O(1). The question is, is 0 O(0) as well?

根据定义，我说是。

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

编辑 3:

Adam Crume使以下 claim :

For any function f(x), f(x) is in O(f(x)).

证明:设S是R的子集，T是R^的子集*(非负实数)并令f(x):S ->T and c ≥ 1. 那么 0 ≤ f(x) ≤ f(x) 导致对于所有 x∈ 0 ≤ f(x) ≤ cf(x) S。因此f(x) ∈ O(f(x)).

具体来说，如果 f(x) = 0 那么 f(x) ∈ O(0) .