分治政策求解遞歸式之主方法

前言：

在之前的文章中筆者介紹了歸并排序，歸并排序的核心思想就是分治，引出了這次筆者關于分治政策的介紹。

正文：

正如在歸并排序中提及的，分治政策中求解問題采用遞歸的方法，每層遞歸分為三個步驟：

• 分解，将問題劃分為規模更小的子問題。
• 解決，遞歸求解出小問題，當小問題規模足夠小時，停止遞歸，直接求解。
• 合并，将小問題的解合并成原問題的解。

當子問題足夠大時，需要繼續遞歸求解，稱之為遞歸情況。

而當子問題規模足夠小時，不需要繼續遞歸，可以進行求解，稱之為基本情況。

注意，有時需要求解與原問題不完全一樣的子問題，将其求解看做合并步驟的一部分。

求解遞歸式的方法有三個：

• 代入法：猜測一個界，然後用數學歸納法證明這個界是正确的。
• 遞歸樹法：将遞歸式轉換為一棵樹，其結點表示不同層次的遞歸調用産生的代價。采用邊界和技術來求解遞歸式。
• 主方法：可求解形如下面公式的遞歸式的界。

T(n)=aT(n/b)+f(n)

其中a>=1,b>1,f(n)是一個給定的函數。它刻畫了這樣一個分治算法，生成a個子問題，每個子問題是原問題規模的1/b，分解和合并步驟花費時間為f(n)。

遞歸式細節

在實際應用中常常會忽略遞歸式聲明和一些技術細節，比如向下取整、向上取整以及邊界條件。

例如，對n個數進行歸并排序，當n為奇數時，兩個子問題的規模精确來說不是n/2而應該分别是，n/2的向下取整與向上取整。而在實際運算和描述其最壞情況運算時間時，我們都忽略了這個細節而直接取n/2進行讨論。

執行個體分析：最大子數組問題（參考自算法導論）

你初次接觸股票看中了一家生物化學公司，而這家公司股票價格不算穩定。你可以在某個時刻買進一股該公司的股票，并在之後的某天賣出，假設你獲得了這家公司未來的價格走向，但是你進行買進賣出都隻能在當天交易結束後進行。用表格的形式展示價格走向：

天數	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
價格	100	113	110	85	105	102	86	63	81	101	94	106	101	79	94	90	97
差價	13	-3	-25	20	-3	-16	-23	18	20	-7	12	-5	-22	15	-4	7

由此可見實際所求即為求一個最大子數組的問題。

采用分治政策，把原數組分為兩個規模盡可能相等的子數組。

而對于最大子數組隻會出現兩種情況：1、完全位于子數組中；2、跨越中點。

具體的代碼實作可參考一下兩篇文章：

最大子數組遞歸和非遞歸(暴力)

最大子數組問題（動态規劃）–【算法導論】

在這裡提一下，筆者正在嘗試在Github上建立自己的部落格，當然是從參考别人的部落格開始一步步慢慢來，當有所成果之後會提供連結，歡迎大家去看。