作者Aa841018 (andrew)
看板Grad-ProbAsk
標題[理工] fractional knapsack時間！
時間Fri Jan 10 23:42:21 2020
課本是寫因為排序要nlogn，所以是nlogn，但用radix sort之類的只要O(n)吧？
那是否代表用非comparsion base的排序就可以降到O(n)?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.52.161.14 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1578670943.A.F2A.html
1F：推 mistel: 前提就是要知道值域 01/11 00:14
2F：推 yang20913: 不可以 01/11 00:17
3F：推 plsmaop: 實數跟有理數有稠密性，fractional 的通常是實數或有理 01/11 09:33
4F：→ plsmaop: 數，有稠密性就不可能用 radix sort ，除非你知道分佈 01/11 09:33
5F：→ Aa841018: 原來是這樣，謝謝各位解釋！ 01/11 10:55
6F：推 alan23273850: 目前為止不限定值域的排序方式還沒發現比nlogn快的. 01/11 21:29
7F：→ mathtsai: 要用到比較大小 就不會比nlogn快 01/12 01:56