推 metalalive:log*n 是 n 取 log 無限次阿, 它只比 O(1) 大 01/22 11:58
→ metalalive:我看錯了 01/22 12:02
→ P568912:為什麼是右邊啊?? 01/22 12:22
→ P568912:不會是相等嗎?! 01/22 12:25
→ wheels:Cormen這版還沒有解答，我也很好奇為啥不是相等XD 01/22 12:27
推 AIdrifter:log有結合律嗎? 01/22 12:28
推 P568912:你有問老師說他們會相等嗎??? 01/22 12:29
→ AIdrifter:我猜測是 一個是對logn取無限log 一個是對最後結果取log 01/22 12:30
→ wheels:問老師後黃子嘉好像一開始也是說相等，不過後來說右邊，洪 01/22 12:31
→ wheels:逸一下子就說右邊，可是問他為啥也說不出為什麼。 01/22 12:31
→ AIdrifter:左邊一開始範圍就只有logn 右邊去只要多取一次log 01/22 12:31
→ wheels:A大想法跟我第二次想法一樣，把它reduce成c和log(c)來看， 01/22 12:32
→ wheels:不過這樣會變成左邊比較大，更詭異了XD 01/22 12:32
推 AIdrifter:恩 我懂你意思@@ 所以我後來想法沒有把他當常數 01/22 12:36
→ AIdrifter:純粹當作取logn無限 和取n無限後再取一個log 01/22 12:37
→ AIdrifter:但是我心裡一直覺得怪怪的 取無限不是一樣嗎?orz 01/22 12:38
→ AIdrifter:這說法也不嚴謹一一" 看看有沒有其他解釋囉 01/22 12:39
推 chunhsiang:課本上的左右邊是相反的 但我覺得是lg*(lgn).... 01/22 13:09
→ Jerrynet:右邊取無限次之後再取log還是等於log*n 01/22 14:23
→ Jerrynet:所以左邊log*(logn)就比右邊log*n小 01/22 14:25
→ chunhsiang:log*n 根據定義它似乎不完全等於取log無限次 01/22 19:48
→ chunhsiang:n = 10^10^...^10 有h個 01/22 19:50
→ chunhsiang:這樣n不管怎麼成長 都是log*(logn)大 ? 01/22 19:51
推 bbhands:可利用 lg*(lg n) = lg*(n)-1 得知lg*(lg n)~lg*(n) 01/25 20:52
→ bbhands:而lg(lg*(n))比lg*(n)慢 所以lg(lg*(n))比lg*(lg(n))慢 01/25 20:54
→ wheels:那要怎麼確定lg(lg*n)會大於1? 01/25 23:26
→ wheels:lg*(n)的遞迴定義我也有考慮過，但是把1移項到另一邊變成 01/25 23:28
→ wheels:lg*(n) = lg*(lg n) + 1，那lg(lg* n) = lg(lg*(lg n) + 1) 01/25 23:29
→ wheels:這樣的話反而會讓lg(lg*(n))變成lg*(lg n)再取一次log，所 01/25 23:30
→ wheels:以變成lg*(lg n)比較大。 01/25 23:31
→ wheels:感覺上這種推法和1比較時還要再多些討論。 01/25 23:33
推 bbhands:你講的結論跟我講的是一樣的 01/26 00:21
→ bbhands:「lg(lg*(n))比lg*(lg(n))慢」vs「lg*(lg n)比較大」 01/26 00:23
推 bbhands:另外lg*(n)遞增無上界，因此lg(lg*(n))>θ(1)是一定的 01/26 00:31
→ wheels:但是這樣推會變成跟老師們說的相反的答案，這才是奇怪的點 01/27 02:07
→ wheels:用遞增無上界來看確實可以發現lg*(n)並非lg取無限次。 01/27 02:14
→ wheels:在n > 某n0時，lg*(lg n) > 1，所以可以推出， 01/27 02:15
→ wheels:lg(lg*(n)) < lg(lg*(lg n) + (lg*(lg n) - 1)lg*(lg n)) 01/27 02:17
→ wheels:= lg((lg*(lg n))^2) = 2 lg(lg*(lg n)) =O(lg(lg*(lg n))) 01/27 02:18
→ wheels:確實就可以推出我們的結果，我也懷疑這就是正確答案= = 01/27 02:19
→ wheels:還是我聽錯老師答案了O_O 01/27 02:20
推 bbhands:剛才確認了一下 這個答案跟Cormen官方提供的解答一樣(2ed) 01/27 12:35
→ wheels:GJ！感謝你！ 01/27 15:28