[理工] 資結 時間複雜度

看板Grad-ProbAsk作者 (zrae)時間11年前 (2012/09/29 22:07), 編輯推噓4(4推 0噓 3→)
留言7則, 4人參與, 最新討論串1/12 (看更多)
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
推
09/30 00:25, , 1F
第二題應該定義帶進去可以觧@@
09/30 00:25, 1F
推
09/30 14:43, , 2F
第一題看不太懂你寫的，lg* n是??
09/30 14:43, 2F
→
09/30 15:04, , 3F
就是lglglglg....很多個lg n
09/30 15:04, 3F
→
09/30 16:06, , 4F
那前後不是一樣意思嗎
09/30 16:06, 4F
推
09/30 19:48, , 5F
lg*n=min{i>=0:lg^(i)n<=1}
09/30 19:48, 5F
→
09/30 19:51, , 6F
lg*n的意思就是說lglgl...lgn要遞迴幾次才會小於等於1
09/30 19:51, 6F
推
09/30 20:05, , 7F
可以參考COMEN第三章
09/30 20:05, 7F
‣ 更多 keke0421 的文章
文章代碼(AID): #1GPm2NqD (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 1 之 12 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共12篇)
‣ 更多 keke0421 的文章
文章代碼(AID): #1GPm2NqD (Grad-ProbAsk)