algorithm - 寻找最高的 2 个数字 - 计算机科学

Question

我正在尝试找出一种算法来找到数字列表中最大的 2 个数字。

最高的数字可以在 n-1 个阶段中找到，也许通过做冒泡排序的第一步或类似的事情。对我来说，似乎也可以在总共 1.5n 次比较中找到下一个最高的数字。

我的教授给我们布置了作业，让我们写一个算法，在 n + log(n) 次比较中找到最高的 2 个数字。这可能吗？有什么想法，建议吗？

编辑:当我说 n + log(n) 时，我指的不是 O(n + log n)，而是 n + log n

Answer 1

是的，可以在不超过 (n + log n) 的时间内完成。如果不给出答案，我真的不能告诉你怎么做，但让我试试。 :-)

取n个数，一次成对比较。取 ceil(n/2) 个“赢家”，然后重复，“就像一棵二叉树”。问题:需要多少次比较才能找到最大的？这个“赢家”赢了多少人？第二大可能输给了谁？那么现在需要多少次比较才能找到第二大的数呢？

答案结果是总计 n-1 + ceiling(log n) - 1 比较，其中 log 以 2 为底。您还可以使用对抗性论证证明它在最坏的情况下不可能做得比这更好。