常数的大O表示法

本文介绍了常数的大O表示法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我计算出我的运行时复杂度为 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.