一般来说,以下内容是否总是正确的?
log(n) = O(na/(a+1))?其中a是任何正整数常数,或许非常大。
如果不是,那么最大的a值是多少才能使此语句成立?
一般来说,以下内容是否总是正确的?
log(n) = O(na/(a+1))?其中a是任何正整数常数,或许非常大。
如果不是,那么最大的a值是多少才能使此语句成立?
然而,你也可以直观地理解它:na/(a+1) 随着 a 变大趋近于 n。自然地,log(n) 总是 O(n)。
log(x) <= log(e) + 1/e * (x-e) = x/e
log(n) = O(n).
log(n) = 1/c * log(n^c) <= 1/(ce) * n^c
C
,都有log(n)=O(n^c)
。log(n)∈O(n^(a/(a+1)))
,对于所有正整数a而言都是正确的,因为a/a+1 < 1 => n^(a/(a+1)) ∈ O(n)
并且因为log(n) ∈ O(n) => log(n) ∈ O(n^(a/(a+1)))
。