作者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/cn.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