algorithm - 帮助大 O 表示法

Question

我在尝试掌握大 O 表示法的概念时遇到了一些问题。所以，根据定义 big O 如下，T(n) ∈ O(G(n)) if T(n) <= G(n) * C .

既然常量“C”可以是任何大于 0 的整数，下面的例子不也是如此吗？

例子:

n log n ∈ O(log n)
n log n <= log n * c

其中 C 等于 n 的值。

我知道答案是n log n ∉ O(log n)但我不明白，因为 C 可以是任何常数。

预先感谢您的帮助:D

Answer 1

c 就是一个常量。这意味着你不能说“让 c 成为 n 的值”，因为你必须先选择一些 c，然后让比较对所有 n 成立。

换句话说，为了使某些 T(n) 成为 O(G(n))，必须存在 没有 常数 c 使得 G(n)*c 大于 T (n) 对于所有 n。

因此 n log n 不是 O(log n)，因为无论您选择什么常数，n > c 都会导致 n log n 大于 c log n。