常量的大 O 表示法
Big O notation of a constant
我计算出我的运行时复杂度为 4，这个的大 O 表示法是什么？
例如，如果我的运行时复杂度是 4 + n，那么它的大 O = O(n)。
让我们粗略地看一下f(n) is in O(g(n))的定义：
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).
您可以像对待任何其他函数一样对待常量函数，w.r.t。使用例如分析其渐近行为大 O 符号。
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:s set membership in O(1)), 而不是 " =12=] 在 O(1)"。但是，您可能希望在 O(1)""（或某些 O(g(n))）中看到不太严格的版本 "f(n)网络，至少在科学文章的范围之外。
我计算出我的运行时复杂度为 4，这个的大 O 表示法是什么？
例如，如果我的运行时复杂度是 4 + n，那么它的大 O = O(n)。
让我们粗略地看一下f(n) is in O(g(n))的定义：
f(n)is inO(g(n))means thatc · g(n)is an upper bound onf(n). Thus there exists some constantcsuch thatf(n) ≤ c · g(n)holds for sufficiently largen(i.e. ,n ≥ n0for some constantn0).
您可以像对待任何其他函数一样对待常量函数，w.r.t。使用例如分析其渐近行为大 O 符号。
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:s set membership in O(1)), 而不是 " =12=] 在 O(1)"。但是，您可能希望在 O(1)""（或某些 O(g(n))）中看到不太严格的版本 "f(n)网络，至少在科学文章的范围之外。