※ 引述《b76516 (阿聰)》之銘言：
: ※ 引述《cormen5566 (怕熱非洲土著)》之銘言：
: ※ 引述《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 <=除了這裡不太懂之外
: ~~~~~~~~~~~~~~~~~~~~~~~~~~ 剩下都懂了 謝謝你
lg(x!) = lg(x * (x-1) * (x-2) *... * 1)
= lg x + lg (x-1) + ... + lg(1) ≦ lg x + lg x + ... + lg x
= O(xlg x)
lg(x!) ≧ lg(x/2) + lg(x/2) + ... + lg(x/2) + 0 + ... + 0
---------------v----------------- -----v-----
x/2個 x/2個
= (x/2)lg(x/2)
= O(xlg x)
將x帶入lgn則
lg((lg n)!) = O(lg n * lg(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
※ 編輯: cormen5566 來自: 140.113.235.131 (11/13 21:00)