資料結構,時間複雜度比大小

Excel實驗

6>4>5~2>1>3

估計是兩個兩個比較

6, 4

用小學時的實驗說明
把大數字分開
20 ==> 4 + 4 + 4 + 4 + 4
20 ==> 5 + 5 + 5 + 5
4^5 = 1024
5^4 = 625 < 1024

具體說是分得越多份乘積越大，最大乘績為每份都是e

y = (A/B)^B
dy/dB = lnB * (A/B)^B
when B = e, dy/dB = 0 = maxima

6比4接近該模式


4, 5

5 實為 N * log(N) 必比 N ^ (logN) 少


5, 2
兩邊 log base k
2: logN
5: logk(N*logN)
= (N*logN) / log(k)
兩近乘 logk
2: log(k) * logN
5: N * logN
N > logk
所以 5 > 2


2, 1
兩邊 log base k
2: logN
1: logk(log(N)^k)
= k * logk(log(N))
= k * log(log(N)) / log(k)
= (k / log(k)) * log(log(N))
故 2>1


1, 3
兩邊 log base log(N)
1: k
3: logblogn(log(N) * (log(k) + (log(log(N))))
=logblogn(log(N)) + logblogn((log(k) + (log(log(N))))
= 1 + logblogn((log(k) + (log(log(N))))
= 1 + (log((log(k) + (log(log(N)))))) / log(N)
其中藍字部份 order 比 log(N)少，故lim n ==> inf 時 3變成1
又因 k > 1
故 1 > 3

2012-02-10 03:03:02 補充：
6>4>5>2>1>3