分治算法

陳新龍

今天我們來學(xué)習(xí)新的Python算法——分治。

分治：我們將一個(gè)復(fù)雜的問題分成兩個(gè)或更多的相同或類似的子問題，再把子問題分成更小的子問題（分），這些子問題可以簡(jiǎn)單地直接求解（治），最后將所有子問題的解合并起來就是原問題的解（合）。

分治算法適用于數(shù)據(jù)規(guī)模較大的問題，通過分治算法，將數(shù)據(jù)分解到多個(gè)小問題，直到找到正確答案為止。

例如我們想求解一個(gè)列表中的最大值或者最小值，為了體會(huì)分治算法，不使用Python中的max（）或min（）函數(shù)，而采用分治函數(shù)來解決。在列表中存在很多數(shù)據(jù)，我們將比較的數(shù)據(jù)不斷縮小再縮小，當(dāng)數(shù)據(jù)規(guī)模為2時(shí)只需一個(gè)判斷就可以找到其中的最小值了。

這個(gè)求最值的問題就變成將若干數(shù)值不斷分組直到兩個(gè)數(shù)據(jù)進(jìn)行比較，通過遞歸把數(shù)據(jù)不斷從中間劃分開，直到其規(guī)模小于等于2時(shí)，比較返回結(jié)果，繼續(xù)通過遞歸到最后兩個(gè)數(shù)據(jù)比較就可以找到最值了。

在這個(gè)程序中對(duì)數(shù)據(jù)使用遞歸的方法拆分?jǐn)?shù)據(jù)，將數(shù)據(jù)分成兩個(gè)部分left_list和right_list，當(dāng)數(shù)據(jù)的規(guī)模等于1的時(shí)候可直接判斷最值，當(dāng)數(shù)據(jù)的規(guī)模等于2的時(shí)候通過比較可以判斷出最值。通過遞歸與分治的方法便求出列表中的最大值是99了。

如果你真正掌握了分治的原理，那么可以嘗試做一道題目：“判斷某個(gè)元素是否在列表中，如果存在，元素輸出，如果不存在，顯示該數(shù)字不存在。”期待你的答案哦。