证明或反证n log\u 10 n(n log\u 2 n)

要记住的主要思想是这个身份:

(log_a x)(log_2 a) = (log_2 x)

(log_a x)(log_2 a) = log_2 a^(log_a x)        ; t(log_2 a) = log_2 a^t
                   = log_2 x                  ; a^(log_a x) = x by definition

为了 a=10 x=n 我们得到:

(log_10 n) = (log_2 n)/(log_2 10)

n

n(log_10 n) = n(log_2 n)/(log_2 10)

然后得到

n(log_10 n) = θ(n(log_2 n))

自从 log_2 10 是一个常数。

返回一个步骤,看看日志库是如何影响复杂性的。