[理工] 104清大計科

看板Grad-ProbAsk作者 (揪立)時間9年前 (2017/01/27 00:19), 編輯推噓5(5推 0噓 20→)
留言25則, 5人參與, 最新討論串2/2 (看更多)
http://i.imgur.com/340KvLh.jpg
想問一下7b的答案應該是多少呢？ http://i.imgur.com/wLGvsFL.jpg
第八題答案有人有嗎QQ Dfn1=8嗎？ http://i.imgur.com/ANCTZDC.jpg
第10要用什麼排序可以在個數個時間內完成？ Radix還是counting可以滿足他呢？ http://i.imgur.com/mdJASKH.jpg
這題時間複雜度應該是多少呢？ 我是猜nlogn 話說有人還有其他題的解答嗎QQ 版上好少人討論清大的題目QQ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.108.131 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1485447566.A.D63.html
→
01/27 00:22, , 1F
搜尋是個好東西
01/27 00:22, 1F
→
01/27 00:54, , 2F
我有找過了QQ
01/27 00:54, 2F
推
01/27 06:21, , 3F
7b.應該是i*(i-1)/2+j-1
01/27 06:21, 3F
→
01/27 06:22, , 4F
第8應該是8 5 5
01/27 06:22, 4F
→
01/27 06:25, , 5F
15題theta(n)吧
01/27 06:25, 5F
→
01/27 08:04, , 6F
10用以n為底的radix sort，把數字都轉成n進制
01/27 08:04, 6F
→
01/27 13:12, , 7F
這樣時間會不會變成kn？
01/27 13:12, 7F
→
01/27 13:19, , 8F
範圍是1~n^2，以n為底的話最多3位數，O(3n)=O(n)
01/27 13:19, 8F
→
01/27 13:20, , 9F
甚至3位數的數字也只有n^2一個數而已，優化一下還可以
01/27 13:20, 9F
→
01/27 13:20, , 10F
變O(2n)
01/27 13:20, 10F
推
01/27 13:35, , 11F
10用n^1/2當basis 用radix sort 包含4次counting sort
01/27 13:35, 11F
→
01/27 13:35, , 12F
,4*O( n(input)+n^1/2(basis的值域）=O(S)
01/27 13:35, 12F
推
01/27 13:42, , 13F
我發現我想錯了，應該D大才是對的
01/27 13:42, 13F
→
01/27 13:49, , 14F
我寫要做5次耶，比如n取100, 取10為base, 範圍為1~10000
01/27 13:49, 14F
→
01/27 13:49, , 15F
，不過10000有5個bit說
01/27 13:49, 15F
→
01/27 13:52, , 16F
用n^1/2當base做radix sort不知道可不可以？
01/27 13:52, 16F
→
01/27 13:53, , 17F
5個bit，數列長度為n^1/2，基底為n^1/2，time complexi
01/27 13:53, 17F
→
01/27 13:54, , 18F
=O(5*(n^1/2+n^1/2))=O(10*n^1/2)=O(n^1/2)=O(|S|)
01/27 13:54, 18F
→
01/27 13:56, , 19F
剛剛忘記考慮base為n的話會比|S|大
01/27 13:56, 19F
→
01/27 13:56, , 20F
應該是5個bit沒錯，不過5個bit只有一個數，可以優化
01/27 13:56, 20F
推
01/27 14:03, , 21F
對耶，寫太快，忘了可以直接先挑出來
01/27 14:03, 21F
→
01/27 14:07, , 22F
但應該也是可以拉，反正都常數
01/27 14:07, 22F
→
01/27 14:11, , 23F
如果1-10000，每個數應該也可以用4個digit 表示，對應
01/27 14:11, 23F
→
01/27 14:11, , 24F
到0-9999 有誤請指正...
01/27 14:11, 24F
推
01/27 14:12, , 25F
我覺得這也是一種優化方法
01/27 14:12, 25F
‣ 更多 joeboy 的文章
文章代碼(AID): #1OYY6ErZ (Grad-ProbAsk)
‣ 更多 joeboy 的文章
文章代碼(AID): #1OYY6ErZ (Grad-ProbAsk)