big-o - Big O 或 Omega 符号中的变量 'C' 指的是什么

Question

在 Big O 或 Omega 表示法中，我理解 n 指的是程序的输入。但是C指代的变量是什么？

Answer 1

虽然很难在不知道在哪里看到 C 的情况下回答这个问题在讨论大 O 符号时，我怀疑它被用来表示某种常量。

例如，您可以使用 C将使用 Big-O 表示法的语句转换为使用谓词逻辑术语的语句:

f(x) = O(g(x)) means:

There exist positive real numbers C and x0, such that for all x >= x0, f(x) <= C * g(x)

选择C因为此处常数倍数的名称完全是任意的。 C很可能只是因为它是“constant”的第一个字母而流行。顶多是约定俗成。

你可以用其他字母，意思是一样的。 Wikipedia page关于这个主题(当时我正在写这篇文章)使用 M在它的大部分方程式中(尽管 C 潜入了页面下方的一些方程式)。您完全有可能看到 C在大 O 表示法的一个描述中，但随后阅读了其他一些未使用 C 的描述完全没有。