如何從n個(gè)數(shù)里找到***值?

很容易想到，用一個(gè)循環(huán)就能搞定。

int find_max(int arr[n]){ 
    int max = -infinite; 
    for(int i=0; i<n; i++) 
        if(arr[i]>max) 
            max=arr[i]; 
    return max; 
} 
  

這里，需要執(zhí)行n-1次比較。

[[255078]]

如何從n個(gè)數(shù)里找到***值與最小值?

很容易想到，用一個(gè)循環(huán)找到***值和最小值，就能搞定。

(int, int) find_max_min(int arr[n]){ 
    int max = -infinite; 
    int min = infinite; 
  
    for(int i=0; i<n; i++){ 
        if(arr[i]>max) 
            max=arr[i]; 
        if(arr[i]<min) 
            min=arr[i]; 
    } 
  
    return (max, min); 
} 

這里，需要執(zhí)行2*(n-1)=2n-2次比較。

還有沒有更快的方法呢?

分治法或許可以派上用場(chǎng)，分治法的思路是：

• 把大規(guī)模拆分成小規(guī)模;
• 小規(guī)模分別求解;
• 小規(guī)模求解之后，再綜合求解大規(guī)模;

看能不能往這個(gè)例子里套用：

• 將arr[0,n]分為arr[0,n/2]和arr[n/2,n];
• 每個(gè)子數(shù)組分別求解***值和最小值;
• 兩個(gè)子數(shù)組的***值里再取***值，兩個(gè)子數(shù)組的最小值里再取最小值，就是最終解;

偽代碼大概是這樣：

(int, int) find_max_min(int arr[0,n]){ 
    // 遞歸左半?yún)^(qū) 
    (max1, min1) = find_max_min(arr[0, n/2]); 
    // 遞歸右半?yún)^(qū) 
    (max2, min2) = find_max_min(arr[n/2, n]); 
  
    // 再計(jì)算兩次 
    max = max1>max2?max1:max2; 
    min = min1<min2?min1:min2; 
  
    return (max, min); 
} 

畫外音，實(shí)際的遞歸代碼要注意：

• 入?yún)⒉皇?和n，而是數(shù)組的下限和上限;
• 遞歸要收斂，當(dāng)數(shù)組的上下限相差1時(shí)，只比較一次，直接返回max和min，而不用再次遞歸;

分治法之后，時(shí)間復(fù)雜度是多少呢?

如果你是“架構(gòu)師之路”的老讀者，《搞定所有時(shí)間復(fù)雜度計(jì)算》一文，能夠輕松求解分治法的時(shí)間復(fù)雜度分析：

(1)當(dāng)只有2個(gè)元素時(shí)，只需要1次計(jì)算就能知道***，最小值

(2)當(dāng)有n個(gè)元素時(shí)，

• 遞歸左半?yún)^(qū);
• 遞歸右半?yún)^(qū);
• 再進(jìn)行兩次計(jì)算;

f(2)=1;【式子A】 
f(n)=2*f(n/2)+2;【式子B】 

求解遞歸式子，得到：

f(n)=1.5n-2; 

畫外音，證明過程如下：

【式子B】不斷展開能得到：

f(n)=2*f(n/2)+2;【式子1】 
f(n/2)=2*f(n/4)+2;【式子2】 
f(n/4)=2*f(n/8)+2;【式子3】 
... 
f(n/2^(m-1))=2*f(2^m)+2;【式子m】 

通過這m個(gè)式子的不斷代入，得到：

f(n)=(2^m)*f(n/2^m)+2^(m+1)-2;【式子C】 
  
由于f(2)=1【式子A】; 
即【式子C】中n/2^m=2時(shí)，f(n/2^m)=f(2)=1; 
此時(shí)n=2^(m+1)，代入【式子C】 
即f(n)=n/2 + n -2 = 1.5n-2; 

證明過程很嚴(yán)謹(jǐn)，但我知道你沒看懂。

建議再看看《搞定所有時(shí)間復(fù)雜度計(jì)算》。

總結(jié)，n個(gè)數(shù)：

• 求***值，遍歷，需要n-1次計(jì)算
• 求***最小值，遍歷，需要2n-2次計(jì)算
• 求***最小值，分治，時(shí)間復(fù)雜度1.5n-2

思路比結(jié)論重要，希望大家有收獲。

【本文為51CTO專欄作者“58沈劍”原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)聯(lián)系原作者】

戳這里，看該作者更多好文