Big O 或 Omega 表示法中的变量 'C' 指的是什么

Question

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

Answer 1

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

例如，您可以使用 C 将使用大 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 可能很受欢迎，因为它是“常量”的第一个字母。顶多是约定俗成。

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