Ste*_*ven 9 algorithm big-o time-complexity
我在尝试掌握大O符号的概念时遇到了一些问题.所以,根据定义,大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
Bor*_*lid 11
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.