分治算法的基本思想是將一個(gè)規(guī)模為N的問(wèn)題分解為K個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題相互獨(dú)立且與原問(wèn)題性質(zhì)相同。求出子問(wèn)題的解，就可得到原問(wèn)題的解，是一種分目標(biāo)完成程序算法，簡(jiǎn)單的問(wèn)題可用二分法完成。

1. 分治算法

        我們?cè)谑褂梅种嗡惴ㄇ蠼鈫?wèn)題的時(shí)候是把一個(gè)問(wèn)題劃分為多個(gè)小問(wèn)題，然后通過(guò)各個(gè)小問(wèn)題的答案來(lái)找到合適的，如果數(shù)據(jù)規(guī)模還是比較大，那么可以再進(jìn)行一次分治算法，直到找到答案為止。

        分治算法的解題步驟一般如下：

        （1）分解，將要解決的問(wèn)題劃分成若干規(guī)模較小的同類問(wèn)題；

        （2）求解，當(dāng)子問(wèn)題劃分得足夠小時(shí)，用較簡(jiǎn)單的方法解決；

        （3）合并，按原問(wèn)題的要求，將子問(wèn)題的解逐層合并構(gòu)成原問(wèn)題的解。

2. 求n個(gè)元素中的最小值

        一個(gè)列表中存在n個(gè)數(shù)據(jù)的時(shí)候，找到其中的最大值，當(dāng)然這個(gè)問(wèn)題我們使用Python可以直接通過(guò)max()函數(shù)和min()函數(shù)來(lái)解決，在這里我們使用分治算法來(lái)解決這個(gè)問(wèn)題。

        問(wèn)題分析，如果這個(gè)問(wèn)題的數(shù)據(jù)規(guī)模小于等于2的時(shí)候，我們可以經(jīng)過(guò)一個(gè)判斷就找到其中的最小值，所以我們需要做的就是想辦法把這若干個(gè)數(shù)據(jù)變成兩個(gè)數(shù)據(jù)進(jìn)行比較，那么我們可以先把數(shù)據(jù)從中間劃分為左右兩部分，然后通過(guò)遞歸再把每一部分再劃分為左右兩部分，直到數(shù)據(jù)規(guī)模小于等于2的時(shí)候，返回結(jié)果，然后通過(guò)遞歸到最后為兩個(gè)數(shù)據(jù)對(duì)比，我們就可以找到最小值。

        代碼如下：

def get_max(number):#尋最小值函數(shù)
    if len(number) == 1
        return number[0]
    else:
        if number[1]>number[0]:
            return number[0]
        else:
            return number[1]
# 分治法
def solve(number):
    n = len(number)
    if n <= 2:  # 數(shù)據(jù)規(guī)模小于等于2使用get_max()函數(shù)
        return get_max(number)
    # 分解（子問(wèn)題規(guī)模為 n/2）
    left_list, right_list = number[:n // 2], number[n // 2:]
    # 遞歸（樹(shù)），分治
    left_max, right_max = solve(left_list), solve(right_list)
    # 合并
    return get_max([left_max, right_max])
if __name__ == "__main__":
    # 測(cè)試數(shù)據(jù)
    test_list = [33,52,2,25,63,75,43,72,45,97,53,25,14,18,3,5]
    # 求出最小值
    print(solve(test_list))

        輸出結(jié)果為：

  2

3. 找到一組數(shù)據(jù)中第 k 小的元素

        代碼如下：

 def divide(number):# 劃分函數(shù)
    fis = number[0]#定義一個(gè)主元
    litter = [x for x in number[1:] if x < fis]#比主元小的元素存放一個(gè)列表
    big = [x for x in number[1:] if x >= fis]#比主元大的元素存放一個(gè)列表
    return fis,litter,big
def find(number,key):# 查找第 k 小的元素
    fis,litter,big = divide(number) #分解
    n = len(litter)
    if n == key:
        return fis#找到
    elif n < key:
        return find(big,key-n-1)#遞歸分治
    else:
        return find(litter,key)#遞歸分治
if __name__ == '__main__':
    list = [3, 45, 18, 65, 53,15,26,37, 27, 49, 17, 93, 0, 100, 13, 62, 52, 7, 24, 29]
    print('第5小的元素:',find(list,5))
    print('第10小的元素:',find(list,10))

        輸出結(jié)果為：

第5小的元素: 17
第10小的元素: 29

4. 總結(jié)

        關(guān)于分治算法，它的實(shí)質(zhì)就是將每個(gè)子問(wèn)題獨(dú)立，然后遞歸求解，來(lái)幫助我們解決數(shù)據(jù)規(guī)模較大的問(wèn)題，它的缺點(diǎn)在于當(dāng)子問(wèn)題不獨(dú)立的時(shí)候就需要求公共子問(wèn)題，所以我們?cè)谶\(yùn)用的時(shí)候一定要考慮一下是否適合分治算法。