Master公式（计算递归复杂度）
Master公式
在计算涉及递归的算法的时候，计算复杂度就会变得有些麻烦。Master公式就是用来进行剖析递归行为和递归行为时间复杂度的估算的
-
Master公式：T(N) = a*T(N/b) + O(N^d)
-
公式解释：n表示问题的规模，a表示递归的次数也就是生成的子问题数，N/b表示子问题的规模。O(N^d)表示除了递归操作以外其余操作的复杂度
-
结论（证明省略）：
①当d②当d=logb a时，时间复杂度为O((N^d)*logN)
③当d>logb a时，时间复杂度为O(N^d) -
注意：子问题规模必须等分，不管你是分成几部分
-
补充阅读：想要了解更多请点击 点我点我
举个例子
下面代码,T(N) = 2 * T(N/2) + O(1)
- 源代码：
package LeetCode;
/*** @Description:* @ProjectNmae: gitTest* @PackageName: LeetCode* @ClassName: test* @Author: Y-peak* @Date: 2021.08.27 15:27 星期五*/public class test {public static void main(String[] args) {int[] arr = new int[]{1,1,2,7,23,4,4};System.out.println(function(arr,1,3));}//求数组arr [L,N] 范围内的最大值public static int function(int[] arr, int L,int R){if(L == R)return arr[L];int mid = L + ((R-L)>>1);int leftMax = function(arr,L, mid);int rightMax = function(arr, mid + 1, R); //两次递归，问题规模等分。return Math.max(leftMax,rightMax);}
}
与上面对比一下，下面的代码：T(N) = 2 * T(N/2) + O(N)
package LeetCode;/*** @Description:* @ProjectNmae: gitTest* @PackageName: LeetCode* @ClassName: test* @Author: Y-peak* @Date: 2021.08.27 15:27 星期五*/public class test {public static void main(String[] args) {int[] arr = new int[]{1,1,2,7,23,4,4};System.out.println(function(arr,1,3));}//求数组arr [L,N] 范围内的最大值public static int function(int[] arr, int L,int R){if(L == R)return arr[L];for (int i = L; i < R; i++) //时间复杂度为 O(N)System.out.println("哎，我就是玩，我就是增加复杂度");int mid = L + ((R-L)>>1);int leftMax = function(arr,L, mid);int rightMax = function(arr, mid + 1, R);return Math.max(leftMax,rightMax);}
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！