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

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

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