关于算法，在最坏情况下,找到N个元素中的第2小元素,要经过多少次比较?请给出答案和证明,(提示:同时找最

来源：百度知道 编辑：UC知道 时间：2024/05/29 15:56:45
做出来一定给加分，谢谢~~
(提示：同时找最小元素)

n+lgn-2 首先两两比较找到最大的元素，需要n-1次，即二叉树的非叶子节点的个数。之后次最大的一定在和最大的元素比较过的元素中，共有lgn-1个，即树的高度。故加起来就是n+lgn-2