常数的大O表示法 [英] Big O notation of a constant

问题描述

我计算出我的运行时复杂度为 4 ，Big O的含义是什么?

I calculate my runtime complexity to be 4, what is the Big O notation of this?

例如，如果我的运行时复杂度为 4 + n ，则其Big O = O(n).

For example if my runtime complexity is 4 + n then its Big O = O(n).

推荐答案

让我们粗略地看一下f(n) is in O(g(n))的定义:

Let's look loosely at the definition of what we mean by f(n) is in O(g(n)):

中的

f(n)表示c · g(n)是f(n)的上限.因此那里 存在一些常量c，使得f(n) ≤ c · g(n)保持 足够大的n(即对于某些常量n0的n ≥ n0).

f(n) is in O(g(n)) means that c · g(n) is an upper bound on f(n). Thus there exists some constant c such that f(n) ≤ c · g(n) holds for sufficiently large n (i.e. , n ≥ n0 for some constant n0).

您可以将常量函数与其他任何函数一样对待.使用例如分析其渐近行为大O表示法.

You can treat a constant function just as any other function, w.r.t. analysing its asymptotic behaviour using e.g. big-O notation.

f(n) = 4
g(n) = 1

f(n) ≤ c · g(n) = c · 1, for c ≥ 4 and for all n           (*)

     (*) with e.g. n0=0 and c=4 => f(n) is in O(1)

---

注意:如Ctx在下面的注释中所述，O(1)(或例如O(n))描述了一组功能，因此要完全正确，应将f描述为在O(1)中(f ∈ O(n)，f:O(1)中的设置成员身份)，而不是"f(n)在O(1)中" .但是，您可能希望看到不太严格的版本"f(n)位于O(1)" (或某些O(g(n)))中，就像在Web上那样频繁，至少在范围之外科学文章.

---

Note: as Ctx notes in the comments below, O(1) (or e.g. O(n)) describes a set of functions, so to be fully correct, f should be described to be in O(1) (f ∈ O(n), f:s set membership in O(1)), rather than "f(n) being in O(1)". You can, however, probably expect to see the less rigorous version "f(n) is in O(1)" (or some O(g(n))) just as frequently at the web, at least outside of the scope of scientific articles.

这篇关于常数的大O表示法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！