[理工] 100清大 計算機科學 第4題

看板Grad-ProbAsk作者 (伐木工)時間10年前 (2014/01/24 20:09), 編輯推噓6(6推 0噓 13→)
留言19則, 6人參與, 最新討論串1/1
想請問一下100年 清大資工的第四題 http://www.lib.nthu.edu.tw/library/department/ref/exam/eecs/cs/100/2201.pdf 感覺是用Radix sort 不知道怎麼下手 麻煩各位幫忙 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.160.71.150
推
01/24 20:33, , 1F
n 進位的 LSD radix sort(bucket sort)。
01/24 20:33, 1F
→
01/24 21:32, , 2F
怎麼看出是 n 進位 這樣會有幾個digit
01/24 21:32, 2F
→
01/24 22:19, , 3F
有幾個 digit 就是，取log_n再+1，比方說看100在10進位
01/24 22:19, 3F
→
01/24 22:19, , 4F
有幾位就取log_10在加1=2。
01/24 22:19, 4F
→
01/24 22:20, , 5F
3
01/24 22:20, 5F
→
01/24 22:22, , 6F
所以，這題的digit數是O(LOGLOG n) 然後要做 n 次。
01/24 22:22, 6F
→
01/24 22:42, , 7F
懂了 感謝~
01/24 22:42, 7F
推
01/26 17:06, , 8F
2^loglog(nlogn) 取log digit數不是O(loglog(nlogn))嗎
01/26 17:06, 8F
→
01/26 17:07, , 9F
還是我看錯或算錯@@還有想問O(d(n+r))是算法 n跟d都知
01/26 17:07, 9F
→
01/26 17:08, , 10F
但r要代什麼呢？？
01/26 17:08, 10F
→
01/26 17:45, , 11F
10進位就代10
01/26 17:45, 11F
→
01/26 17:45, , 12F
n跟logn之間沒括號，r 是幾進位。
01/26 17:45, 12F
推
01/26 17:56, , 13F
呃 那為何不是O(loglogn．logn)呢 還是取log的某處可刪
01/26 17:56, 13F
→
01/26 17:57, , 14F
掉？？我很怕是自己數學問題 是的話很sorryQQ
01/26 17:57, 14F
→
01/26 18:09, , 15F
2^log(logn*logn)=(logn*logn)^log2 取log可得到
01/26 18:09, 15F
→
01/26 18:09, , 16F
log(logn*logn)=loglogn+loglogn=O(loglogn)…
01/26 18:09, 16F
推
01/26 18:36, , 17F
對不起哈哈 謝謝你們我懂了
01/26 18:36, 17F
推
02/10 21:34, , 18F
不是2^(loglogn )xlogn=(2^logn)^loglogn=n^loglogn
02/10 21:34, 18F
推
02/10 21:36, , 19F
因此取n 爲base,對n^loglogn取log_n+1得到loglogn嗎？
02/10 21:36, 19F
‣ 更多 FaMuGong 的文章
文章代碼(AID): #1IubWMQM (Grad-ProbAsk)