五個函數如何比較其大小

這應該是考慮 n 大時的順序, 也就是看各函數成立速度.

一般而言,
指數成長 > 冪數成長 > 對數成長.

3^{log_2(n)} = 2^{log_2(n)log_2(3)} = n^{log_2(3)} ≒ n^{0.4771-0.3010}
= n^{0.1761} < n

故 for large n,
log_2(log_2(n)) < (log_2(n))^2 < 3^{log_2(n)} < n*log_2(n) < n√n


2011-03-20 23:16:00 補充：
錯字更正: "成立速度"→"成長速度"

2011-03-21 12:04:25 補充：
計算式有錯, 致結論錯誤.

3^{log_2(n)} = 2^{log_2(n)log_2(3)} = n^{log_2(3)} ≒ n^{0.4771/0.3010}
≒ n^{1.58} > n√n

故順序應修正為:
log_2(log_2(n)) ＜ (log_2(n))^2 ＜ n*log_2(n) ＜ n√n ＜ 3^{log_2(n)}

Let s=log_2(n) < = > n=2^s.
Then 3^log_2(n)=3^s
and n√n=n^(3/2)
=(2^s)^(3/2)
=2^((3/2)s)
=[2^(3/2)]^s
=(√8)^s
< (√9)^s
=3^s.
So n√n < 3^log_2(n).