※ 引述《mqazz1 (无法显示)》之铭言： : 我想请教一题演算法.. : Show that the second smallest of n elements : can be found in (n+logn-2) comparisons in the worst case. : 找第二小的元素 : 在最差状况下 : 可以使用 n + logn - 2 次比较找到 : 请问这题应该从哪个部份下手会比较方便呢? 我看过的做法如下: 先把 n 个元素每两个放在一组, 每一组做一次比较取出较小的元素 o o <= 底层每两个元素比较, 较小者胜出 / \ / \ o o o o <= 原本有 n 个元素, 放在底层 然後把每一组取出的较小元素继续两两一组, 每一组做一次比较取出较小的元素 o / \ / \ o o / \ / \ o o o o 这样直到取得最小元素, 共做了 n-1 次比较 --- 因为每次比较恰好淘汰一个元素. 接着, 第二小元素一定有与最小元素比较过 --- 因为第二小元素在上面那个 tree 里面, 最终没有胜出 (i.e., 被放到顶上), 这一定是被最小元素打败的. 而与最小元素做过比较的元素顶多 lg n 个, 在这 lg n 个里面取最小的元素只要 lg n-1 次比较, 这也就是全部 n 个数里面的第二小数! 总共比较次数为 n-1 + lg n - 1 --

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