Phi*_*lip 5 sorting algorithm comparison performance runtime
给定n个数字,如何使用最多n + log(n)比较找到最大和第二大数字？
请注意,它不是O(n + log(n)),而是n + log(n)比较.
use*_*0.1 11
帕伊顿发表了评论.
让我详细说明一下.
正如帕顿所说,这可以通过比赛选择来完成.
可以认为这是一场淘汰单打网球锦标赛,其中球员的能力有严格的顺序,比赛的结果完全取决于该顺序.
在第一轮中,有一半人被淘汰出局.在下一轮另一半等(可能有一些脚趾).
最终赢家将在最后一轮和最后一轮决出胜负.
这可以看作是一棵树.
树的每个节点将成为该节点的子节点之间匹配的赢家.
叶子是球员.第一轮的获胜者是叶子的父母等.
这是n个节点上的完整二叉树.
现在按照获胜者的路径.赢家已经进行了log n匹配.现在考虑那些log n匹配的输家.其中第二好的必须是最好的.
获胜者将以n-1场比赛决定(每场比赛击出一场),并且在logn -1场比赛中决定胜负.
因此,你可以决定n + logn中最大和第二大的比较.
事实上,它可以证明这是最佳的.在最坏情况下的任何比较方案中,获胜者必须参加登录比赛.
为了证明假设一个点系统,在一场比赛之后,获胜者获得了输家的分数.最初都是从每个1点开始.
最后,最终获胜者有n分.
现在给出任何算法,它可以被安排,以便具有更多积分的玩家总是赢家.由于任何人的得分在该场景中的任何比赛中最多为两倍,因此在最坏的情况下至少需要获胜者所玩的log n匹配.