概述
强调一点，所有的递归方法都可以通过循环方法替代，只是递归从逻辑上更容易理解。
Master公式只适用于子问题的规范是一致的，不然无法写成a*T(N/b)。
公式
概念
形如
T(N) = a * T(N/b) + O(N^d) （其中a,b,d都是常数）的递归函数，可以直接通过Master公式来确定时间复杂度。
如果log(b,a) < d，复杂度O(N^d)；
如果log(b,a) > d，复杂度O(N^log(b,a))；
如果log(b,a) == d，复杂度为O(N^d * logN)；
注意：N是处理的总元素数量。
Master公式只关注递归函数整体逻辑，不需要层层的进入递归函数。
N/b表示整体是一次处理的元素个数，a表示元素整体上分成几部分处理，O(N^d)表示合并分支数据的复杂度。
示例
递归版的归并排序。
Master公式说明：
N是arr数组元素的总数。
a = 2，递归方法整体上分成左、右两个分支。
b = 2，每个部分是N/2，所以b为2。
O(N^1)是分支合并的时间复杂度，因此d=1。
所以：log(2,2) == 1，满足log(b,a) = d的公式，
所以归并排序的时间复杂度为O(N * logN)。
我们下面来看归并排序的例子：
package com.study.algorithm.recursion;
public class ArraySort {
public static void main(String[] args) {
int[] arr = {1, 3, 9, 18, 5, 6, 7, 13, 22, 19, 38, 39, 61, 89};
recursionSort(arr, 0, arr.length - 1);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + ",");
}
}
public static void recursionSort(int[] arr, int left, int rigth) {
// base case
if (left == rigth) {
return;
}
int middle = left + ((rigth - left) >> 2);
recursionSort(arr, left, middle);
recursionSort(arr, middle + 1, rigth);
// 合并分支数据的逻辑
int[] mergerArr = new int[rigth - left + 1];
int i = left;
int j = middle + 1;
int index = 0;
while (i <= middle && j <= rigth) {
mergerArr[index++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
}
while (i <= middle) {
mergerArr[index++] = arr[i++];
}
while (j <= rigth) {
mergerArr[index++] = arr[j++];
}
System.arraycopy(mergerArr, 0, arr, left, rigth - left + 1);
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/99932.html
