greedy - 时间复杂度为“nlogn”的给定未排序输入的贪心算法

Question

多约束背包问题

我有这样一个给定的例子，我只是想理解，O（n * logn）的贪心算法和O（n2）的贪心算法有什么区别？我真的不知道如何开始请帮助！我应该对其进行排序还是不同的东西:(？（利润和重量比不是按递减或递增的顺序排列，完全随机）p =（p1；：：：；pn）=（24；17；95；103；41； 39; 22; 1) w = (w1; : : : ;wn) = (20; 15; 39; 41; 27; 23; 18; 2)

Answer 1

是的，O(n log n) 算法是按（利润/重量）降序排序，然后尽可能多地抓取物体，直至达到重量限制。当然，排序算法必须是 O(n log n)。

天真的 (O(n^2)) 算法将重复搜索列表中具有最高（利润/重量）比率的项目并抓住它。请注意，这实际上与进行选择排序相同。