Comparing Time Complexity

Yao Yao on August 3, 2020

Question: Sort the following terms from slowest growing to fastest growing.


这题其实非常 tricky。

首先要注意两点:

  • $2^{\log_2 n} = n$
  • $5^{\log_3 n} = n^{\log_3 5}$

所有我们上来可以排列成 3 组:

  • $(\log_2 n + 1)^3 < 1000 (\log_2 n)^3$
  • $n^{\frac{1}{2}} < 2^{\log_2 n} < n \log n$
  • $5^{\log_3 n} < n^{\log_3 7} < 7^{2n} < 2^{7n}$

我们事后诸葛亮一下:这个问题可以转化为证明下面两个不等式:

  • $1000 (\log_2 n)^3 < n^{\frac{1}{2}}$
  • $n \log n < 5^{\log_3 n}$

1. 不等式一

令 $f(n) = 1000 (\log_2 n)^3 - n^{\frac{1}{2}}$。令 $n = 2^{2k}$,于是得到:$f(n) = 8000k^3 - 2^k$

这个很明显 $\underset{k \to +\infty}{\lim} 8000k^3 - 2^k = -\infty$

所以:$(\log_2 n)^3 < n^{\frac{1}{2}}$

2. 不等式二

令 $f(n) = n \log n - 5^{\log_3 n} = n \log n - n^{\log_3 5}$。令 $n=2^k$,于是得到:$f(n) = 2^k k - 2^{k \times \log_3 5} = 2^k (k - 2^{({\log_3 5} - 1) \times k})$

因为 $\log_3 5 - 1 > 0$,所以 $\underset{k \to +\infty}{\lim} k - 2^{({\log_3 5} - 1) \times k} = -\infty$

所以:$n \log n < 5^{\log_3 n} $

3. 综上



blog comments powered by Disqus