[理工] [algo] complexity

看板Grad-ProbAsk作者時間14年前 (2012/01/22 11:55), 編輯推噓9(9推 0噓 35→)
留言44則, 8人參與, 最新討論串1/1
Cormen的習題: log*(logn)和log(log*n)誰的成長速率比較大？ 問過黃子嘉跟洪逸，兩個都說右邊，但是都說不出為什麼@@ 有人上課的時候老師提過嗎？ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 111.249.8.59
推
01/22 11:58, , 1F
log*n 是 n 取 log 無限次阿, 它只比 O(1) 大
01/22 11:58, 1F
→
01/22 12:02, , 2F
我看錯了
01/22 12:02, 2F
→
01/22 12:22, , 3F
為什麼是右邊啊??
01/22 12:22, 3F
→
01/22 12:25, , 4F
不會是相等嗎?!
01/22 12:25, 4F
→
01/22 12:27, , 5F
Cormen這版還沒有解答，我也很好奇為啥不是相等XD
01/22 12:27, 5F
推
01/22 12:28, , 6F
log有結合律嗎?
01/22 12:28, 6F
推
01/22 12:29, , 7F
你有問老師說他們會相等嗎???
01/22 12:29, 7F
→
01/22 12:30, , 8F
我猜測是 一個是對logn取無限log 一個是對最後結果取log
01/22 12:30, 8F
→
01/22 12:31, , 9F
問老師後黃子嘉好像一開始也是說相等，不過後來說右邊，洪
01/22 12:31, 9F
→
01/22 12:31, , 10F
逸一下子就說右邊，可是問他為啥也說不出為什麼。
01/22 12:31, 10F
→
01/22 12:31, , 11F
左邊一開始範圍就只有logn 右邊去只要多取一次log
01/22 12:31, 11F
→
01/22 12:32, , 12F
A大想法跟我第二次想法一樣，把它reduce成c和log(c)來看，
01/22 12:32, 12F
→
01/22 12:32, , 13F
不過這樣會變成左邊比較大，更詭異了XD
01/22 12:32, 13F
推
01/22 12:36, , 14F
恩 我懂你意思@@ 所以我後來想法沒有把他當常數
01/22 12:36, 14F
→
01/22 12:37, , 15F
純粹當作取logn無限 和取n無限後再取一個log
01/22 12:37, 15F
→
01/22 12:38, , 16F
但是我心裡一直覺得怪怪的 取無限不是一樣嗎?orz
01/22 12:38, 16F
→
01/22 12:39, , 17F
這說法也不嚴謹一一" 看看有沒有其他解釋囉
01/22 12:39, 17F
推
01/22 13:09, , 18F
課本上的左右邊是相反的 但我覺得是lg*(lgn)....
01/22 13:09, 18F
→
01/22 14:23, , 19F
右邊取無限次之後再取log還是等於log*n
01/22 14:23, 19F
→
01/22 14:25, , 20F
所以左邊log*(logn)就比右邊log*n小
01/22 14:25, 20F
→
01/22 19:48, , 21F
log*n 根據定義它似乎不完全等於取log無限次
01/22 19:48, 21F
→
01/22 19:50, , 22F
n = 10^10^...^10 有h個
01/22 19:50, 22F
→
01/22 19:51, , 23F
這樣n不管怎麼成長 都是log*(logn)大 ?
01/22 19:51, 23F
推
01/25 20:52, , 24F
可利用 lg*(lg n) = lg*(n)-1 得知lg*(lg n)~lg*(n)
01/25 20:52, 24F
→
01/25 20:54, , 25F
而lg(lg*(n))比lg*(n)慢 所以lg(lg*(n))比lg*(lg(n))慢
01/25 20:54, 25F
→
01/25 23:26, , 26F
那要怎麼確定lg(lg*n)會大於1?
01/25 23:26, 26F
→
01/25 23:28, , 27F
lg*(n)的遞迴定義我也有考慮過，但是把1移項到另一邊變成
01/25 23:28, 27F
→
01/25 23:29, , 28F
lg*(n) = lg*(lg n) + 1，那lg(lg* n) = lg(lg*(lg n) + 1)
01/25 23:29, 28F
→
01/25 23:30, , 29F
這樣的話反而會讓lg(lg*(n))變成lg*(lg n)再取一次log，所
01/25 23:30, 29F
→
01/25 23:31, , 30F
以變成lg*(lg n)比較大。
01/25 23:31, 30F
→
01/25 23:33, , 31F
感覺上這種推法和1比較時還要再多些討論。
01/25 23:33, 31F
推
01/26 00:21, , 32F
你講的結論跟我講的是一樣的
01/26 00:21, 32F
→
01/26 00:23, , 33F
「lg(lg*(n))比lg*(lg(n))慢」vs「lg*(lg n)比較大」
01/26 00:23, 33F
推
01/26 00:31, , 34F
另外lg*(n)遞增無上界，因此lg(lg*(n))>θ(1)是一定的
01/26 00:31, 34F
→
01/27 02:07, , 35F
但是這樣推會變成跟老師們說的相反的答案，這才是奇怪的點
01/27 02:07, 35F
→
01/27 02:14, , 36F
用遞增無上界來看確實可以發現lg*(n)並非lg取無限次。
01/27 02:14, 36F
→
01/27 02:15, , 37F
在n > 某n0時，lg*(lg n) > 1，所以可以推出，
01/27 02:15, 37F
→
01/27 02:17, , 38F
lg(lg*(n)) < lg(lg*(lg n) + (lg*(lg n) - 1)lg*(lg n))
01/27 02:17, 38F
→
01/27 02:18, , 39F
= lg((lg*(lg n))^2) = 2 lg(lg*(lg n)) =O(lg(lg*(lg n)))
01/27 02:18, 39F
→
01/27 02:19, , 40F
確實就可以推出我們的結果，我也懷疑這就是正確答案= =
01/27 02:19, 40F
→
01/27 02:20, , 41F
還是我聽錯老師答案了O_O
01/27 02:20, 41F
推
01/27 12:35, , 42F
剛才確認了一下 這個答案跟Cormen官方提供的解答一樣(2ed)
01/27 12:35, 42F
→
01/27 15:28, , 43F
GJ！感謝你！
01/27 15:28, 43F
→
09/11 14:47, , 44F
= lg((lg*(l https://daxiv.com
09/11 14:47, 44F
‣ 更多 wheels 的文章
文章代碼(AID): #1F6uYLMZ (Grad-ProbAsk)