- 相關(guān)推薦
PHP算法學(xué)習(xí)之分治法
分治法，顧名思義就是分而治之，即把問(wèn)題拆解為性質(zhì)相同的小問(wèn)題再處理。下面小編為大家整理了PHP算法學(xué)習(xí)之分治法，希望能幫到大家！
做了一些題后發(fā)現(xiàn)，分治法除了分治，名字里還少了一步，那就是合，也就是怎樣通過(guò)小問(wèn)題的答案得到拆分之前大問(wèn)題的答案。
分治法的時(shí)間復(fù)雜度：分治法并沒(méi)有像二分法一樣每次丟掉一半無(wú)用的解，它只是做了分離，而分離的兩部分都是需要處理的，所以分治法的時(shí)間復(fù)雜度是O(n)。特例情況是當(dāng)分離的兩部分繼續(xù)分治處理出現(xiàn)重復(fù)計(jì)算的情況時(shí)，就會(huì)比O(n)大了！所以請(qǐng)確保你的分治盡量不要出現(xiàn)重疊計(jì)算的情況。
那么什么問(wèn)題適合用分治的思想解決呢？二叉樹(shù)！二叉樹(shù)這種左右子樹(shù)的結(jié)構(gòu)天生就非常適合分治，所以它的大部分問(wèn)題都能用分治解決，碰到一個(gè)問(wèn)題你只需要問(wèn)問(wèn)左子樹(shù)你怎么處理，右子樹(shù)你怎么辦，得到左右子樹(shù)的答案后，你再想想最后的答案是個(gè)啥~除了二叉樹(shù)，快速排序歸并排序這兩個(gè)著名的排序算法也是分治的思想。下面就舉幾個(gè)解題的例子來(lái)加深一下對(duì)分治法的學(xué)習(xí)。
1、前序遍歷二叉樹(shù)
2、求二叉樹(shù)的最大路徑和
給一棵二叉樹(shù)，找出從根節(jié)點(diǎn)出發(fā)的路徑中，和最大的一條。
這條路徑可以在任何二叉樹(shù)中的節(jié)點(diǎn)結(jié)束，但是必須包含至少一個(gè)點(diǎn)。
3、求最近公共祖先
給定一棵二叉樹(shù)，找到兩個(gè)節(jié)點(diǎn)的最近公共父節(jié)點(diǎn)(LCA)，給出的兩個(gè)節(jié)點(diǎn)都在樹(shù)中存在。
4、快速排序
這里我就偷個(gè)懶，直接貼出百度百科上給的php標(biāo)準(zhǔn)答案~
【PHP算法學(xué)習(xí)之分治法】相關(guān)文章：
php算法學(xué)習(xí)之動(dòng)態(tài)規(guī)劃08-18
php算法學(xué)習(xí)之寬度優(yōu)先搜索07-29
php學(xué)習(xí)之php配置07-15
PHP紅包算法11-04
php經(jīng)典算法介紹10-05
PHP經(jīng)典算法題09-05
php學(xué)習(xí)之php預(yù)定義變量07-29
PHP幾個(gè)經(jīng)典算法題10-27