作者keke0421 (zrae)
看板Grad-ProbAsk
標題[理工] 資結 時間複雜度
時間Sat Sep 29 22:07:17 2012
1. which is asymptotically larger lg(lg* n) or lg*(lgn)?
我自己是認為 前者大於後者
理由是 lg*(lgn)就算裡面lgn是超大的數 ex: 2*(65536) 基本上也是才5
成長超慢 雖然前者也一樣慢。當然這是我的猜測 不知道怎麼用嚴謹的方式解決
2.Show that klnk = θ(n) implies k = θ(n/lnn).
這個想了老半天還是沒頭緒~"~
麻煩各位大大惹
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.37.138.219
推 xling5216:第二題應該定義帶進去可以觧@@ 09/30 00:25
推 fenir:第一題看不太懂你寫的，lg* n是?? 09/30 14:43
→ Bearcome:就是lglglglg....很多個lg n 09/30 15:04
→ Murasaki0110:那前後不是一樣意思嗎 09/30 16:06
推 xling5216:lg*n=min{i>=0:lg^(i)n<=1} 09/30 19:48
→ xling5216:lg*n的意思就是說lglgl...lgn要遞迴幾次才會小於等於1 09/30 19:51
推 xling5216:可以參考COMEN第三章 09/30 20:05