[理工] fractional knapsack時間！

[Aa841018 (andrew)]

課本是寫因為排序要nlogn，所以是nlogn，但用radix  sort之類的只要O(n)吧？
那是否代表用非comparsion base的排序就可以降到O(n)?

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.52.161.14 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1578670943.A.F2A.html
推 mistel: 前提就是要知道值域
推 yang20913: 不可以
推 plsmaop: 實數跟有理數有稠密性，fractional 的通常是實數或有理
→ plsmaop: 數，有稠密性就不可能用 radix sort ，除非你知道分佈
→ Aa841018: 原來是這樣，謝謝各位解釋！
推 alan23273850: 目前為止不限定值域的排序方式還沒發現比nlogn快的.
→ mathtsai: 要用到比較大小 就不會比nlogn快