中位数为O（n log n）的Quicksort

我真的不明白为什么我们不总是选择中间元素作为支点。这可以在O（n）中完成，因此导致总运行时间为O（n log n）。 我只是假设在中位数搜索的O（n）中可能隐藏了一个大常量。     
2019-10-28 4 条评论
分享

没有找到相关结果

    已邀请:

    公藕

    从Wikipedia Quicksort页面：   相反，一旦我们知道最坏情况下的选择算法可用，我们就可以使用它在快速排序的每一步找到理想的枢轴（中位数），从而产生具有最坏情况O（n log n）运行时间的变体。然而，在实际实现中，该变体平均来说相当慢。 换句话说，强制保证O（n log n）的成本通常不值得付出。有关该页面以及选择算法页面的更多信息。     
    2019-10-28 0 0
    分享

    才脊烽馈低

    使用随机快速排序，你有最坏的运行时间O（n log n），概率非常高。     
    2019-10-28 0 0
    分享

    棠媳鳖

    显然，使用随机版本的分区，找到中位数的运行时间似乎是O（n），但实际上当分区再次在其极端不平衡时，运行时间变为O（n2）。所以你不能从这里做任何改进。 但仍有希望。如果你通过“CORMEN”那么你会发现即使在最坏的情况下，也可以在线性时间内找到第i个订单统计数据。使用的技术是使用中位数作为枢轴元素，然后找到保证线性运行时间的nedian。 因此我们也可以在quicksort中使用该技术来获得O（nlgn）运行时间     
    2019-10-28 0 0
    分享
    为什么被折叠? 0 个回复被折叠

    要回复问题请先登录或注册

    或代码 OrCode.com 备案号：粤ICP备15020848号-1
    Escape time: 0.046957015991211