※ 引述《b76516 (阿聰)》之銘言：
: 請問一下
: 在洪逸跟洪捷的演算法名校攻略秘笈1-20頁
: 1/logn
: 2= n 這條式子是用兩邊取log比較得到等號還是用log的公式而得到的？
lg 2 lg n
因為n = n = 2 (*)
1/lg n lgn * (1/lg n)
=> n = 2 = 2
: √2logn √2/logn （開根號是整個2logn一起開根號,後面則是2/logn開根號）
: 2 ＝n 這條式子又是怎麼來的
同(*)
√(2/lg n) lg n * √(2/lg n) √(2lg n)
=> n = 2 = 2
: logn √2logn
: √2 跟2 這兩個的時間複雜度怎麼比大小呢？
lg n lg 2
√2 = n = n ---(1)
√2logn √2/logn
2 = n ---(2)
=> (1) ≧ (2)
: 3 loglogn
: (logn)!的時間複雜度為什麼夾在n 跟n 之間呢？
3
lg((lg n)!) = lg n* lglg n ≧ lg n = 3 lg n
: 1-22頁的範例2
: (4) 3 ln n
: f(n)=n g(n)= 8
: 為什麼f(n)=O(g(n))
ln n ln 8 3
g(n) = 8 = n ≦ n = f(n)
=> g(n) = O(f(n))
: 問題有點多 先謝謝大家的回答
算到頭有點昏~有錯請指出囉!!!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.235.131