共计 2348 个字符,预计需要花费 6 分钟才能阅读完成。
遇到递归算法,通常有两个问题:
- 分析递归行为
- 估算递归行为的工夫复杂度
应用树状剖析图能够帮忙咱们分析递归行为。
应用 Master Theorem 及其推论(也称主定理)能够不便的估算某些递归的工夫复杂度。
这里次要针对第二个问题,如何针对某类递归,应用 master 公式估算工夫复杂度。
主定理
先来看下公式以及论断:
先了解公式外面每一项代表的意义:
等号右边 T(N) 是母问题的数据量,规模为 N
。
等号左边的 T(N/b) 是子问题的规模
,子问题的规模是 等量
的,规模为 N/b
;系数 a 是子问题被调用的次数
;O(N^d) 是指除了子问题的递归调用之外,剩下的运算的工夫复杂度
。
满足以上形容的递归,能够应用主定理来估算工夫复杂度。
上面应用两个例子来训练一下。
例 1
写一个递归办法,来找到数组中的最大值。
static int findMax(int[] arr) throws IllegalArgumentException{if (arr == null || arr.length == 0) throw new IllegalArgumentException("invalid.");
if (arr.length == 1) return arr[0];
return recursion(arr, 0, arr.length - 1);
}
private static int recursion(int[] arr, int from, int to) {if (from == to) return arr[from];
int mid = from + (to - from) / 2;
int left = recursion(arr, from, mid);
int right = recursion(arr, mid + 1, to);
return Math.max(left, right);
}
在下面的问题中,母问题总量是 N,也就是数组的长度;递归函数中,子问题被调用了两次,也就是系数 a =2,别离用来计算左半子数组和右半子数组的最大值,规模是等量的,都是是 N /2;剩下的操作就是 if 判断,计算 mid 值,返回 left 和 right 较大值,这些操作的工夫复杂度是常数 O(1)。齐全满足主定理的场景。T(N) = 2 * T(N/2) + O(N^0)
: a=2, b=2, d=0.
log(b,a) = log(2,2) = 1 > d = 0, 所以用推论间接得出复杂度是T(N)=O(N).
例 2
用主定理来估算归并排序算法的复杂度。
归并排序先递归地将数组分成两半,别离排序,而后将后果归并起来。算法如下:
public class MergeSort {static void mergeSort(int[] arr) {if (arr == null || arr.length < 2) return;
sort(arr, 0, arr.length - 1);
}
static void sort(int[] arr, int left, int right) {if (left >= right) return;
int mid = left + (right - left) / 2;
sort(arr, left, mid);
sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
private static void merge(int[] arr, int left, int mid, int right) {int[] help = new int[right - left + 1];
// 1. 把 arr[left, mid]和 arr[mid+1, right]两个子数组归并到辅助数组
// a 指向第一个子数组的起始地位,b 指向第二个子数组的起始地位,指向辅助数组的起始地位
int i = 0, a = left, b = mid + 1;
// 在 a 和 b 不越界的状况下,比拟所指的元素,把较小的那个放到辅助数组中
while (a <= mid && b <= right) {help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
}
// 若 a 不越界,阐明 b 曾经越界,把右边的子数组剩下的元素顺次放入辅助数组
while (a <= mid) {help[i++] = arr[a++];
}
// 若 b 不越界,阐明 a 曾经越界,把左边的子数组剩下的元素顺次放入辅助数组
while (b <= right) {help[i++] = arr[b++];
}
// 2. 把辅助数组中的元素拷贝回 arr 数组
for (i = 0; i < help.length; i++) {arr[left + i] = help[i];
}
}
static boolean checkSorted(int[] arr) {if (arr.length < 2) return true;
for (int i = 1; i < arr.length; i++) {if (arr[i] < arr[i - 1]) return false;
}
return true;
}
public static void main(String[] args) {
int n = 1000000;
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = (int) (Math.random() * n);
mergeSort(arr);
System.out.println(checkSorted(arr));
}
}
母问题总量是数组长度 N,在递归体中子问题规模相等,都是 N /2,调用了两次;判断语句和计算 mid 语句是常数级运算 O(1),merge 办法的复杂度是 O(N), 因为在 merge 中,最坏的状况是把数组所有元素往辅助数组中放一遍,又从辅助数组往原数组中放一遍,所以复杂度是 O(N)。
这种状况满足主定理条件,T(N)=2T(N/2)+O(N), a = 2, b = 2, d = 1
.
利用推论 log(b,a)=1 和 d 相等,所以间接计算复杂度T(N)=O(N*logN).
留神:若子问题规模不相等,则不合乎应用主定理的条件。