@目錄
- 1.定義
- 2.適用條件分析
- 3.步驟
- 應用1：歸并排序
- 步驟
- 演算法
- 演算法分析
- 應用2：快速排序
- 基本思想
- 演算法
- 演算法分析
- 參考
分治法（Divide and Conquer）
1.定義
對于具備以下特點的問題：
- 原問題可以分解為若干個與原問題性質相類似的子問題
- 問題的規模縮小到一定程度后可方便求出解
- 子問題的解可以合并得到原問題的解
- 分解出的各個子問題應相互獨立
當這類問題較復雜或規模較大時，將它分解為若干子問題，通過合并子問題的解得到原問題的解，
2.適用條件分析
分治法所能解決的問題一般具有以下幾個特征：
- 該問題的規模縮小到一定的程度就可以容易地解決
- 該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質
- 利用該問題分解出的子問題的解可以合并為該問題的解
- 問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題
上述的第一條特征絕大多數問題都可以滿足，第二條是分治法應用的前提，反映了遞回思想的應用，
第三條特征是關鍵，如果具備了第一條和第二條特征，而不具備第三條特征，則可以考慮貪心演算法
或動態規劃演算法；第四條特征涉及到分治法的效率，如果各個子問題不是獨立的，則分治法要重復
地解公共子問題，動態規劃演算法解決效率更高，動態規劃法=分治演算法思想+解決子問題冗余情況
3.步驟
- 分解
- 求解子問題
- 合并子問題的解
應用1：歸并排序
步驟
- 把具有n個元素的陣列分解為二個n/2大小的子陣列
- 遞回地分解子陣列，直到子陣列只包含一個元素為止
- 合并已排好序的子陣列使之成為一個新的排好序的子陣列，重復合并直到得到原問題的解
演算法
演算法分析
應用2：快速排序
基本思想
在當前的無序區A[p..r]中任取一個元素x作為比較的基準，并用該基準將當前無序區分為左右二個
較小的無序區A[p..q-1]和A[q+1..r]，使得左邊的無序區A[p..q-1]中的元素均小于基準元素x，
右邊的無序區A[q+1..r]中的元素均大于x，
演算法
quicksort(A,p,r）
if p<r
q=patition(A,p,r)
quicksort(A,p,q-1)
quicksort(A,q+1,r)
partition(A,p,r)
x=A[r]
i=p-1
for j=p to r-1
if A[j]≤x
i=i+1
exchange(A[i],A[j])
exchange(A[i+1],A[r])
return i+1
演算法分析
partition演算法時間為： θ(n) --> Quicksort的時間：T(n) = T(q)+T(n-q-1)+ θ(n)
最壞情況：二個無序區的大小分別為n-1和0，T(n) = θ(n^2)
最好情況：O(nlgn)
參考
《演算法導論》
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/79580.html
標籤：其他
上一篇：跟我一起學演算法——動態規劃
下一篇：跟我一起學演算法——二項堆