本篇文章涉及公式，由于博客園沒有很好的支持，建議移步我的CSDN博客和簡書進行閱讀，
1. Master公式是什么？
我們在解決演算法問題時，經常會用到遞回，遞回在較難理解的同時，其演算法的復雜度也不是很方便計算，而為了較為簡便地評估遞回的演算法復雜度，Master公式應運而生，下面給出Master公式的維基百科鏈接
1.1 Master公式
$T(N) = a*T(\frac{N}{b}) + O(N^d)$
- a：子問題被呼叫的次數
- $\frac{N}{b}$：子問題的規模
- N：母問題的規模
- d：額外操作的次數
- 當$log_{b}a < d$時，$O(N^d)$；
- 當$log_{b}a > d$時，$O(N^{log_{b}a})$；
- 當$log_{b}a = d$時，$O(N^d*logN)$；
2. Master公式的應用舉例
使用遞回求最大值
-
代碼
public static int maxNum(int[] arr, int L, int R){ if(L == R) { return arr[L]; } int mid = L + ((R - L) >> 1); int lMax = maxNum(arr, L, mid); int rMax = maxNum(arr, mid + 1, R); return Math.max(lMax, rMax); } -
決議：如上是求陣列中的最大值的方法，將陣列劃分成左半部和右半部，求出左邊最大值，在求出右邊的最大值，最后比較左右的最大值，求出整個陣列的最大值，因為將陣列劃分為左右兩部分，所以子問題的規模為$\frac{N}{2}$，即b = 2，又有
int lMax = maxNum(arr, L, mid)和int rMax = maxNum(arr, mid + 1, R)的兩次呼叫，所以a = 2，剩下來，有return arr[L]、int mid = L + ((R - L) >> 1)、return Math.max(lMax, rMax)三個常數級的操作，所以d = 0，將a,b,d代入，則其Master公式可表示為：$T(N) = 2 * T(\frac{N}{2}) + O( 1 )$
根據Master公式，$log_b{a} = log_2{2} = 1 > d = 0$，所以，復雜度為$O(N^{log_ba}) = O(N)$
3. 注意事項
使用Master公式分析遞回問題復雜度時，各子問題的規模應該是一致的，否則不能使用Master公式，
本人系菜鳥一枚，所寫文章皆為學習總結，大佬請輕噴??
謝謝閱讀??，歡迎補充！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/6696.html
標籤：其他