Q: 對于一個由N個整數(shù)數(shù)組，需要比較多少次才能把最大和最小的數(shù)找出來呢？
A: 這個還算是比較容易，遍歷一次，就可以找出最大值和最小值，把他們當(dāng)做是兩個單獨的事件來進行處理，O(2n)的時間復(fù)雜度；
Scheme0：尋找數(shù)組中的最大值和最小值看成是兩個獨立的問題，對它們分別求解：

O(2*N)

Scheme1: 一般最大的數(shù)和最小的數(shù)不會是同一個數(shù)，（除非N= 1，或者所有的數(shù)都是一樣大）
==》將數(shù)組中的數(shù)分成兩個部分，再從這兩個部分中分別找出最大的數(shù)和最小的數(shù)目。
1 34 45 4 6 7 8 ==》（1 ，34）（5 ，4）（6 ，7）（8）【兩個數(shù)為一組】這個只是概念上的分類；
在同一組中奇數(shù)和偶數(shù)位數(shù)字，將比較大的數(shù)放在偶數(shù)位上，較小的數(shù)放在奇數(shù)位上。通過N/2次比較之后，較大的數(shù)放在偶數(shù)位置上，較小的數(shù)放在奇數(shù)上 較大=》偶數(shù)位 較小=》奇數(shù)位；
上面就變成了： 1 34 4 5 6 7 8 ，
最后從奇數(shù)位置上求出min = 1，偶數(shù)位置求出max = 34 ，各需要N/2次，整個算法共需要1.5*N次。

代碼

可以看到時間復(fù)雜度已經(jīng)減少了0.5N 。
scheme2: 上一種方式破壞了原來數(shù)組的結(jié)構(gòu)，下面一種方法，保持數(shù)組原來的結(jié)構(gòu)，時間復(fù)雜度還是1.5N;
就是將相鄰的分為一組，還是一樣；將同一組中較大的和max比較，較小的和min比較；

代碼

schem3: 采用分治法，有待思考；
思路： 只需要分別求出前后N/2個數(shù)的min和max ，然后去較小的min，較大的max即可。
【時間復(fù)雜度是：1.5N-2，并沒有省多少】

分治法的偽代碼

拓展： 找出N個數(shù)中的第二大數(shù)，需要比較多少次？【是否可以同樣使用分治法】
思路：
1、可以先找出最大的數(shù)目，然后就是在找最大的數(shù)目，這樣最大最小的數(shù)目的時候都會增加一倍，一般的方法；
2、如果使用分治法，這個也時間也未必減少，最后聊個比較并不一定是最大和第二大的數(shù)進行對比的；
3、新排序，然后去第二大的數(shù)目，這個時間就為排序的時間復(fù)雜度了；最快的排序的時間復(fù)雜度也要nlogN;

時間復(fù)雜度是N

【這個種方法循環(huán)了一次】