※ 引述《Leon (Achilles)》之铭言： : ※ 引述《kao028kimo (羊羽)》之铭言： : : 已知现在有n个不相同的数 : : 题目要求找出第二大的数 需要做几次的比较？ : : 我的作法： : : 先找出最大的数 : : 由数字之中挑选两数做比较 再由剩下来的n-2个数全部挑上来比较 : : 所以需要花n-1次的比较 : : 现在问题来了 : : 题目(其实是演算法的回家作业)要求 : : Show that to find the second largest number requires at least n-2+logn : : comparisons : : 也就是说 : : 在n-1个数中挑最大的数至少要logn-1 comparisons : : 以上就是我最不解的部份 : : 究竟那个log是怎麽产生的呢？ : 这个, 用中文来说, : 第二名只会输给第一名. : 所以你只要把输给第一名的人找出来, 然後叫他们互比就行了. : 在产生第一名的过程中的输家, 有 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次) --

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