是空的算法O（0）的时间复杂度？ [英] Is the time complexity of the empty algorithm O(0)?

问题描述

因此​​，考虑下面的程序：

---

这是程序O（0）的时间复杂度？换句话说，就是0 O（0）？

我以为回答这个在一个单独的问题，将一些线索这个问题

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

解决方案

从维基百科：

一个功能的大O符号方面的描述通常只提供了一个上限函数的增长速度。

从这个描述中，由于空算法要求0的时间来执行，它为O的上限性能（0）。这意味着，它也是O（1），这恰好是一个更大的上限。

修改：

更正式地从CLR（1ED，第26页）：

对于一个给定函数先按g （ N ），我们定义 0 （先按g （<我> N ））的函数集

0 （先按g （ N ））= { F （ N ）：存在正的常数 C 和 N <子> 0 ，使得0乐; F（N）与乐; CG （ N ）的所有 N ＆GE; N <子> 0 }

空算法的渐近时间的表现，在执行0时不管输入的，因此成员 0 （0）。

编辑2

我们都同意，0为O（1）。现在的问题是，是0 O（0）呢？

根据定义

，我说是的。

另外，我觉得有一点意义的问题比许多答案表示。就其本身而言空的算法可能是毫无意义的。然而，每当规定的一个非平凡算法是，空算法可以被认为之前为位于连续步骤的算法之间的指定以及和算法步骤之后。很高兴知道，无并不影响算法的渐近时间的表现。

修改3

亚当Crume 作出如下<一个href="http://stackoverflow.com/questions/3209139/is-the-time-complexity-of-the-empty-algorithm-o0/3215301#3215301">claim:

对于任何函数 F （ X ）， F （ X ）是O（ ˚F（ X ））。

证明：让取值是的一个子集 - [R 和 T 是一个子集研究 ^* （非负实数），并让 F （ X ）：取值 - > T 和<我> C ＆GE; 1，然后0乐; F （ X ）和乐; F （ X ），这导致0乐; F （ X ）和乐; CF （ X ）的所有x∈取值。因此， F （ X ）∈O（ F （ X ））。

具体而言，如果 F （ X ）= 0，那么 F （ X ）∈O（0）

So given the following program:

---

Is the time complexity of this program O(0)? In other words, is 0 O(0)?

I thought answering this in a separate question would shed some light on this question.

EDIT: Lots of good answers here! We all agree that 0 is O(1). The question is, is 0 O(0) as well?

解决方案

From 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.

From this description, since the empty algorithm requires 0 time to execute, it has an upper bound performance of O(0). This means, it's also O(1), which happens to be a larger upper bound.

Edit:

More formally from CLR (1ed, pg 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₀ }

The asymptotic time performance of the empty algorithm, executing in 0 time regardless of the input, is therefore a member of O(0).

Edit 2:

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

Based on the definitions, I say yes.

Furthermore, I think there's a bit more significance to the question than many answers indicate. By itself the empty algorithm is probably meaningless. However, whenever a non-trivial algorithm is specified, the empty algorithm could be thought of as lying between consecutive steps of the algorithm being specified as well as before and after the algorithm steps. It's nice to know that "nothingness" does not impact the algorithm's asymptotic time performance.

Edit 3:

Adam Crume makes the following claim:

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

Proof: let S be a subset of R and T be a subset of R^* (the non-negative real numbers) and let f(x):S ->T and c ≥ 1. Then 0 ≤ f(x) ≤ f(x) which leads to 0 ≤ f(x) ≤ cf(x) for all x∈S. Therefore f(x) ∈ O(f(x)).

Specifically, if f(x) = 0 then f(x) ∈ O(0).

这篇关于是空的算法O（0）的时间复杂度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！