算法：分而治之（应用快速排序？！）

有关如何处理下面问题的任何帮助，我们将不胜感激。我也发布了一些关于这个问题的想法。算法：分而治之（应用快速排序？！）

你是一个招收n名学生的班级的助教。您有他们的最终成绩（未排序），并且您必须为他们指定一个可用成绩（A，B，C等）。约束条件（假设n是多的G）：

究竟（N/G）学生获得每个等级（对于例如，如果n = 30，以及G = {A，B，C} ，那么正好10名学生获得A， 10 GET B和10获得C）

较低分数的学生没有得到一个更高档次比具有较高分数（但是学生，他们可能会相同年级）假设每个学生获得不同的分数，导出了一个有效的算法，并根据n 和G给出其复杂度。首先对分数进行排序的任何算法都将接收z ero credit。

我的回答：好了，问题的最后一行说，我也不好，如果我尝试了数组排序第一和划分阵列为G等份。当使用最佳排序算法时，这将花费O（n log n）。所以，我想到了一个复杂的解决方案。我认为这个问题是一个快速排序可以派上用场的例子，因为我们不需要对同一年级的学生进行排序，我们可以有k个关键元素，关键元素都是等距的。但是，我们没有得到学生的评分，我们也被告知每个学生都有不同的分数。

首先，我使用MaxMin分而治之算法计算最大和最小分数，这将花费O（n）时间。使用最大值和最小值，我们可以通过计算大致找出每个等级的关键要素。（最大 - 最小）/ k =最小等级，2 *（最大 - 最小）/ k =第二最低等级。和k-1 *（最大 - 最小）/ k =最高等级。

现在使用这些作为关键元素，我们可以只执行快速排序的分区方法，第一次需要n个时间量，n-（最大 - 最小）/ k第二次，等等。所以算法的时间复杂度为O（n），因为min-max问题的复杂度为O（n），而Quick Sort中的Partition的复杂度为O（n）。

请分享您的想法。

来源

2015-02-08 whyme

我们的具体问题是什么？ – 2015-02-08 18:12:34

“假设每个学生获得不同的分数，导出一个有效的算法，并根据n和G给出它的复杂度”是否有不同/更好的方法来解决我所缺少的这个问题。我的想法是对的吗？ – whyme 2015-02-08 18:17:26

我不确定这是否有效，因为它假设分数均匀分布在[min;最大。假设得分是[1,2,3,4,5,6,20] – BlackBear 2015-02-08 18:21:34

您可以将所有分数放在（最大）优先级队列中，然后从中提取n/G组。这仍然是一个隐含的排序，但仍然不被规则所禁止。

来源

2015-02-08 20:27:52 BlackBear

这基本上是一个选择问题，只是你一次做G选择。

http://en.wikipedia.org/wiki/Quickselect算法的修改应该在这里工作。尽管Quicksort总是递归地下降到两个分区，并且原始Quickselect仅下降到包含第k个索引的那个分区，但是该问题的算法应当下降到分区当且仅当它包含n/G,2*n/G,(G-1)*n/G数组中的一个索引 - 分级之间的分数。

这些索引是等级之间的分裂点，所以最终得到的是一个数组，其中分裂点之间的元素不一定是排序的，但是这些点之间的块是。

来源

2015-02-08 20:41:44

算法：分而治之（应用快速排序？！）

回答

相关问题