找出N個數(shù)組中第二大的數(shù)，需要比較多少次？比較次數(shù)最少的理論從n個數(shù)中找出最大的兩個數(shù)是：n logn-2分析1：類似于競爭推廣，配對比較，勝者再次配對，最后得到冠軍（最大數(shù)），這可以看作是一個二叉樹

找出N個數(shù)組中第二大的數(shù)，需要比較多少次？

比較次數(shù)最少的理論從n個數(shù)中找出最大的兩個數(shù)是：n logn-2分析1：類似于競爭推廣，配對比較，勝者再次配對，最后得到冠軍（最大數(shù)），這可以看作是一個二叉樹。以4個人為例：0020123，我們可以看到比較的最大次數(shù)是n-1。那么第二大的數(shù)字必須是與冠軍相比的數(shù)字，所以很明顯，每層有一個，所以有l(wèi)ogn-1比較。所以總共是n logn-2比較。分析二：泡泡法找出最大比較數(shù)是n-1，然后在前面的每次比較結果中找出第二大數(shù)，比較數(shù)是logn，需要減去最后一次比較的最大數(shù)，即找到第二個數(shù)是logn-1，結果是n logn-2。