algorithm - Big Theta 表示法中的常数值

Question

在 Big Theta 表示法中，每个 ? 值的常数c1和不同。c2n

定义：

Theta(g(n)) = {f(n): there exist c1 >= 0, c2 > 0 and n0 > 0
                     such that for all n >= n0,
                     0 <= c1, g(n) <= f(n) <= c2 * g(n)}

Answer 1

c1并且c2对于 的每个值都没有不同n。如果它们是，它们将依赖于n，并且不会是常量。

Answer 2

Theta(g(n)) = {f(n): for all n >= n0, there exist c1 >= 0, c2 > 0 and n0 > 0
                 such that 0 <= c1, g(n) <= f(n) <= c2 * g(n)}

我不认为你定义中的量词是正确的。它应该是

Theta(g(n)) = {f(n): there exist c1 >= 0, c2 > 0 and n0 > 0
                 such that for all n >= n0, c1 * g(n) <= f(n) <= c2 * g(n)}