首页 文章

算法:分而治之(快速排序的应用?!)

提问于
浏览
2

关于如何处理下面的问题的任何帮助将不胜感激 . 我也对这个问题发表了一些看法 .

您是一个招收n名学生的 class 的助教 . 你有他们的最终分数(未分类),你必须为他们分配一个G可用等级(A,B,C等) . 约束是(假设n是G的倍数):完全(n / G)学生得到每个年级(例如,如果n = 30,G = {A,B,C},那么正好10个学生得到A,得分为10,得分为10)得分较低的学生得分不高于得分较高的学生(但是,他们可能达到相同的等级)假设每个学生得到的分数不同,那么得分高算法并给出其在n和G方面的复杂性 . 任何首先对分数进行分类的算法都将获得零信用 .

我的回答:好的,问题的最后一行说如果我首先尝试对数组进行排序并将数组分成G等份,我就不好了 . 当使用最佳排序算法时,这将花费O(n log n) . 所以,我想到了一个错综复杂的解决方案 . 我认为这个问题是一个快速排序可以派上用场的例子,因为我们不需要对属于同一等级的学生进行排序,我们可以有k个关键元素,而关键元素都是等间距的 . 但是,我们没有得到学生的分数,我们也被告知每个学生都有不同的分数 .

首先,我使用MaxMin Divide and Conquer算法计算最大和最小分数,这将花费O(n)时间 . 使用最大值和最小值,我们可以通过计算粗略地找到每个等级的关键元素 . (最大 - 最小)/ k =最低等级,2 *(最大 - 最小)/ k =第二最低等级 . 和k-1 *(最大 - 最小)/ k =最高等级 .

现在使用这些作为关键元素,我们只能执行快速排序的分区方法,第一次需要n次,第二次是n-(Max-Min)/ k,依此类推 . 因此,算法的时间复杂度将是O(n),因为最小 - 最大问题具有复杂度O(n)并且快速排序中的分区具有O(n)的复杂度 .

请分享你的想法 .

2 回答

  • 1

    您可以将所有分数放在(最大)优先级队列中,然后从中提取n / G组 . 这仍然是一种隐含的排序,但是规则并未禁止 .

  • 1

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

    http://en.wikipedia.org/wiki/Quickselect算法的修改应该在这里工作 . 虽然Quicksort总是递归地下降到两个分区,而原始的Quickselect只下降到包含第k个索引的那个,但是当这个问题包含 n/G2*n/G ,... (G-1)*n/G 数组之一时,这个问题的算法应该下降到一个分区 . 索引 - 在分数之间分割点的索引 .

    这些索引是等级之间的分割点,因此您最终会得到一个数组,其中分割点之间的元素不一定要排序,但这些点之间的块是 .

相关问题