一哀峻、基本概念
在計(jì)算機(jī)科學(xué)中涡相，分治法是一種很重要的算法。字面上的解釋是“分而治之”剩蟀，就是把一個(gè)復(fù)雜的問題分成兩個(gè)或更多的相同或相似的子問題催蝗，再把子問題分成更小的子問題……直到最后子問題可以簡(jiǎn)單的直接求解，原問題的解即子問題的解的合并育特。這個(gè)技巧是很多高效算法的基礎(chǔ)生逸，如排序算法(快速排序，歸并排序)且预，傅立葉變換(快速傅立葉變換)……
任何一個(gè)可以用計(jì)算機(jī)求解的問題所需的計(jì)算時(shí)間都與其規(guī)模有關(guān)。問題的規(guī)模越小烙无，越容易直接求解锋谐，解題所需的計(jì)算時(shí)間也越少。例如截酷，對(duì)于n個(gè)元素的排序問題涮拗，當(dāng)n=1時(shí)，不需任何計(jì)算迂苛。n=2時(shí)三热，只要作一次比較即可排好序。n=3時(shí)只要作3次比較即可三幻，…就漾。而當(dāng)n較大時(shí)，問題就不那么容易處理了念搬。要想直接解決一個(gè)規(guī)模較大的問題抑堡，有時(shí)是相當(dāng)困難的。
二朗徊、基本思想及策略
分治法的設(shè)計(jì)思想是：將一個(gè)難以直接解決的大問題首妖，分割成一些規(guī)模較小的相同問題，以便各個(gè)擊破爷恳，分而治之有缆。
分治策略是：對(duì)于一個(gè)規(guī)模為n的問題，若該問題可以容易地解決（比如說規(guī)模n較形虑住）則直接解決棚壁，否則將其分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題形式相同铸豁，遞歸地解這些子問題灌曙，然后將各子問題的解合并得到原問題的解。這種算法設(shè)計(jì)策略叫做分治法节芥。
如果原問題可分割成k個(gè)子問題在刺，1<k≤n逆害，且這些子問題都可解并可利用這些子問題的解求出原問題的解，那么這種分治法就是可行的蚣驼。由分治法產(chǎn)生的子問題往往是原問題的較小模式魄幕，這就為使用遞歸技術(shù)提供了方便。在這種情況下颖杏，反復(fù)應(yīng)用分治手段纯陨，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解留储。這自然導(dǎo)致遞歸過程的產(chǎn)生翼抠。分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中获讳，并由此產(chǎn)生許多高效算法阴颖。
三、分治法適用的情況
分治法所能解決的問題一般具有以下幾個(gè)特征：
1) 該問題的規(guī)呢はィ縮小到一定的程度就可以容易地解決
2) 該問題可以分解為若干個(gè)規(guī)模較小的相同問題量愧，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。
3) 利用該問題分解出的子問題的解可以合并為該問題的解帅矗；
4) 該問題所分解出的各個(gè)子問題是相互獨(dú)立的偎肃，即子問題之間不包含公共的子子問題。
第一條特征是絕大多數(shù)問題都可以滿足的浑此，因?yàn)閱栴}的計(jì)算復(fù)雜性一般是隨著問題規(guī)模的增加而增加累颂；
第二條特征是應(yīng)用分治法的前提它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應(yīng)用尤勋；喘落、
第三條特征是關(guān)鍵，能否利用分治法完全取決于問題是否具有第三條特征最冰，如果具備了第一條和第二條特征瘦棋，而不具備第三條特征，則可以考慮用貪心法或動(dòng)態(tài)規(guī)劃法暖哨。
第四條特征涉及到分治法的效率赌朋，如果各子問題是不獨(dú)立的則分治法要做許多不必要的工作，重復(fù)地解公共的子問題篇裁，此時(shí)雖然可用分治法沛慢，但一般用動(dòng)態(tài)規(guī)劃法較好。
四达布、分治法的基本步驟
分治法在每一層遞歸上都有三個(gè)步驟：
step1 分解：將原問題分解為若干個(gè)規(guī)模較小团甲，相互獨(dú)立，與原問題形式相同的子問題黍聂；
step2 解決：若子問題規(guī)模較小而容易被解決則直接解躺苦，否則遞歸地解各個(gè)子問題
step3 合并：將各個(gè)子問題的解合并為原問題的解身腻。