做酒水网站陕西有哪些/广州seo优化费用

master method（主定理）

假设有递推关系式 $T(n)=aT(\frac{n}{b})+f(n)$ ，其中 $n$ 为问题的规模，$a$ 为递推的子问题数量，$\frac{n}{b}$ 为每个子问题的规模（假设每个子问题的基本规模基本一样），$f(n)$ 为递推以外进行的计算工作。

$a\ge 1,b>1$ 为常数，$f(n)$ 为函数，$T(n)$​ 为非负整数。则有以下结果（分类讨论）：

（1）若 $f(n)=O(n^{lo{g}_{b}a-\epsilon })$ ，$\epsilon >0$ ，那么 $T(n)=\Theta (n^{lo{g}_{b}a})$

（2）若 $f(n)=\Theta (n^{lo{g}_{b}a})$ ，那么 $T(n)=\Theta (n^{lo{g}_{b}a}logn)$

（3）若 $f(n)=\Omega (n^{lo{g}_{b}a+\epsilon })$ ，$\epsilon >0$ ，且对于某个常数 $c<1$ 和所有充分大的 $n$ 有 $af(\frac{n}{b})\le cf(n)$ ，那么 $T(n)=\Theta (f(n))$

注：摘自百度百科，主定理。

主定理翻译

简单翻译下：

对于递推关系式 $T(n)=aT(\frac{n}{b})+f(n)$​ 可以分为三种情况讨论 $T(n)$​ 等于多少。

第一种情况

如果 $f(n)=O(n^{lo{g}_{b}a-\epsilon })$​ ，$\epsilon >0$​ ，那么时间复杂度就是 $T(n)=O(n^{lo{g}_{b}a})$​

可能会觉得明明就是 $T(n)=\Theta (n^{lo{g}_{b}a})$ ，怎么变成 $T(n)=O(n^{lo{g}_{b}a})$

这个应该是个数学问题，可以简单理解成一切 $\Theta (f(n))$ 都是 $O(f(n))$ ，但是不可以反过来。

这个暂时没想到现成的代码例子（想到了就补上）。就举个抽象的例子吧。

比如 $T(n)=4\times T(\frac{n}{2})+n$

我们通过递推式可以得到 $a=4,b=2,f(n)=n$

我们先计算下 $n^{lo{g}_{b}a}$ 显然 $n^{lo{g}_{b}a}=n^2$

$f(n)=n=O(n^{2-1})$ 因此我们得到 $\epsilon =1>0$ 符合第一种情况。

故 $T(n)=O(n^2)$ 即时间复杂度式 $O(n^2)$

注意：这里的 $T(n)$ 是递归函数的执行时间。

第二种情况

如果 $f(n)=\Theta (n^{lo{g}_{b}a})$ ，那么 $T(n)=\Theta (n^{lo{g}_{b}a}logn)$

第一种情况已经讲的很详细了，现在直接举具体的例子-我们熟知的快速排序

主要代码部分：

void quick_sort(int arr[], int low, int high) {if (low >= high) {return;}int mid = split(arr, low, high);quick_sort(arr, low, mid - 1);quick_sort(arr, mid + 1, high);
}

我们设 $T(n)$ 为 quick_sort 的执行时间。

则 $T(n)=n+T(\frac{n}{2})+T(\frac{n}{2})=2T(\frac{n}{2})+n$

我们先计算下 $n^{lo{g}_{b}a}$​​ 显然 $n^{lo{g}_{b}a}=n=f(n)$​ 满足第二种情况。

那么 $T(n)=(nlogn)$ 即时间复杂度 $O(nlogn)$

第三种情况

如果 $f(n)=\Omega (n^{lo{g}_{b}a+\epsilon })$ ，$\epsilon >0$ ，且对于某个常数 $c<1$ 和所有充分大的 $n$ 有 $af(\frac{n}{b})\le cf(n)$ ，那么 $T(n)=\Theta (f(n))$

举个抽象例子吧 $T(n)=2T(\frac{n}{2})+n^2$

我们先计算下 $n^{lo{g}_{b}a}$​ 显然 $n^{lo{g}_{b}a}=n$​

$f(n)=n^2=\Omega (n^{1+1})$ 因此我们得到 $\epsilon =1>0$ 且对于某个常数 $c<1$ 和所有充分大的 $n$ 有 $af(\frac{n}{b})\le cf(n)$

对于后面这个 且对于某个常数 $c<1$​ 和所有充分大的 $n$​ 有 $af(\frac{n}{b})\le cf(n)$​​ ​ 只要我们的 $c\in (\frac{1}{2},1)$​ 就可以满足 $af(\frac{n}{b})\le cf(n)$

所以 $T(n)=\Theta (f(n))$ 即是时间复杂度为 $O(n^2)$​

总结

主定理被描述为解决这种递推的“天下无敌法”(master method)，对于我们分析递归的时间复杂度是超级有帮助的。

也并不是所有的递归都可以用主题定理推出来。（比如说汉诺塔问题，斐波那契数列等，他们的递推式显然并不满足主定理的递推式，根据严蔚民版的数据结构上的方法，我们直接暴力递推就好了）

此外，还有一种分析递归时间复杂度的方法叫做 recusion tree 递归树分析法，以后有时间再介绍吧。