大O符号的帮助

2018-06-13 22:47:22

我试图掌握大O符号的概念时遇到了一些问题。所以，根据定义， T(n) ∈ O(G(n)) if T(n) <= G(n) * C ，则大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

c就是这样一个常数。这意味着你不能说“让c是n的值”，因为你必须首先选择一些c，然后让这个比较适用于所有的n。

换句话说，为了使一些T（n）为O（G（n）），必须不存在常数c，使得对于所有n，G（n）* c大于T（n）。

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

让我重复你的话。

c可以是任何常数。

这意味着c不能依赖于n。

这个想法是，不平等对于任何n和固定的c都是成立的。所以虽然你可能发现某个特定的c使得n log n <c log n（即任意c> n），但你可以很容易地找到其他n'不适用的n'（即n'> c）。

链接地址: http://www.djcxy.com/p/39731.html