算法:分治算法

分治算法的基本步驟:

1.分解

將問題劃分成一些子問題,子問題的形式與原問題一樣,只是規模更小。

2.解決

遞歸的求解出子問題。如果子問題的規模足夠小,停止遞歸,直接求解。

3.合併

將子問題的解組合成原問題的解。

算法的複雜度是O(nlogn)

舉例:

歸併排序

對一個亂序的數組[14,12,15,13,11,16]進行排序。

1.分解

將數組分解成兩個數組A[14,12,15]和B[13,11,16]。這兩個數組被之前的數組規模更小,是原數組規模的一半,另外子問題的形式也一樣,對這兩個數組進行排序。在拆分成子問題時,一般會採用折半的方式,這樣兩邊的規模相似,總體的複雜度是最小的。

2.解決

可以繼續拆分兩個數組,將兩個數組再分別拆分成兩個數組,如此繼續下去。當拆分到每個小子數組只剩一個元素的時候,就停止遞歸,直接求解。對於單個元素的數組本身就是有序的。

3.合併

需要將兩個排序好的數組進行合併。可以採用這種方式:構建一個空的數組C,比較A數組的第一個元素和B數組的第一個元素,將較小著放入數組C。當數組A和B中的一個數組先被遍歷完時,將另一個數組的剩餘元素全部順序的放入C。數組C即為排序好的數組。

算法:分治算法

歸併排序原理示意圖

分治算法是比較常用的算法,在處理大規模問題的時候,可以嘗試將其分解成更小規模的問題進行處理,之後再將結果合併。


分享到:


相關文章: