※ 引述《Lucemia (生の直感、死の予感)》之铭言： : ※ 引述《Leon (Achilles)》之铭言： : : 这个, 用中文来说, : : 第二名只会输给第一名. : : 所以你只要把输给第一名的人找出来, 然後叫他们互比就行了. : : 在产生第一名的过程中的输家, 有 log(n) 个. : 把淘汰树画出来就很清楚了: : O : / \ : O 3 : / \ / \ : O 2 .... : / \/ \ : O 1 ..... : 假设 O是最後的胜利者，也就是最大的数 (需要比较 n-1 次) : 因为第二大的数只比最大的数小，所以一定是被O淘汰掉的 : 以这个图来说, N=8时 就是1, 2, 3 下的数字其中之一 (共 log(n)个) : 因此只要求在1,2,3中的最大数, 就是所要的 : 全部中第二大的数 (需要 比较log(n) -1次) 有人问, exist ~= at least, 我想了一下, 这的确不太好证明, 不过, exist 就代表了 at most. Say, if there exist a algorithm, smaller than n + log n - 2. Assume we only have {a,b} two elements.. than.. need 0 comparision! 如果你要比较分析的证明, 你可以画一 tree, 代表 parial relation. 假设 {a,b,c,d} 四个 element, 在三次比较後, we have a > b, c > d, a > c. then it will like a b c d 而我们最後希望建构 relation tree a b c d 你必须去比较 a 的 child. 我已经忘记这个 operation 的名词了, btw, 这边你就可以看到, 为何第一步需要采用淘汰赛的形式. -- 赵客缦胡缨，吾钩霜雪明。银鞍照白马，飒沓如流星。 十步杀一人，千里不留行。是了拂衣去，深藏身与名。 闲过信陵饮，脱剑膝前横。将炙啖朱亥，持觞劝侯赢。 三杯吐然诺，五岳倒为轻。眼花耳热後，意气素霓生。 就赵挥金锤，邯郸先震惊。千秋二壮士，烜赫大梁城。 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 76.170.72.148