递归方程T(n)=aT(n/b)+f(n)之通用解法

在算法设计中经常需要通过递归方程估计算法的时间复杂度T(n)，本文针对形如T(n)=aT(n/b)+f(n)的递归方程进行讨论，以期望找出通用的递归方程的求解方式。

算法设计教材中给出的Master定理可以解决该类方程的绝大多数情况，根据Master定理：o-渐进上界、w-渐进下界、O-渐进确界。

设a≥1，b＞1为常数，f(n)为函数，T(n)=aT(n/b)+f(n)为非负数,令x=logba：

1.       f(n)=o(nx-e)，e＞0，那么T(n)=O(nx)。

2.       f(n)=O(nx)，那么T(n)=O(nx logn)。

3.       f(n)=w(nx+e)，e＞0且对于某个常数c＜1和所有充分大的n有af(n/b)≤cf(n)，那么T(n)=O(f(n))。

然而，Master定理并没有完全包括所有的f(n)的情况。注意到条件1和3中的e总是大于0的，所以在条件1和2、条件2和3之间存在所谓的“间隙”，使得某些f(n)在该情况下不能使用该定理。因此，我们需要找到在Master定理不能使用的情况下如何解递归方程的比较通用的办法——递归树。

经过分析，递归树解法包含了Master定理，但是Master定理可以方便的判断出递归方程的解。产生这种结果的原因关键在于f(n)的形式，显然，当f(n)是n的多项式p(n)形式的话必然满足Master定理的要求，但是f(n)不是多项式就需要另当别论了。

下面就题目所列出的递归方程形式进行分析。

一、f(n)是n的多项式p(n)=f(n)

因为f(n)是多项式，设p(n)=O(nk)，k≥0。根据递归树计算方式，有：

              T(n)= aT(n/b)+nk 。

              T(n/b)= aT(n/b2)+(n/b)k 。

              T((n/b2)= aT(n/b3)+( n/b2)k 。

              ……

       于是得到：T(n)= nk (1+ a/ bk + (a/ bk)2 + (a/ bk)3 +···+ (a/ bk)h)，h=logbn。

       1：logba=k

              这种情况下a/ bk= 1，显然T(n)= O(nk logbn)。

       2：logba≠k

              此时等比数列公比不是1，根据等比数列求和公式化简得到：

T(n)=( nk –nx)/(1-a/bk)，x=logba。

如果logba<k，则T(n)= O(nk)。

如果logba>k，则T(n)= O(nx)。x=logba。

       通过以上的计算表明，在Master定理的条件中，针对f(n)为多项式的情况可以使用递归树的方法进行证明和计算。同样，在f(n)不是多项式的时候也可以通过的这种方式得到方程的解。

二、f(n)是一般函数

当f(n)不是n的多项式的时候，计算就会变得比较复杂，有时可能会也找不到最终的解。但是递归树的方法给我们一种更好使用的解决办法。下面根据一个简单的例子说明这一点：

当a=b=2、f(n)=nlgn时候（lgn:log2n的简记），计算递归方程的解。

T(n)= 2T(n/2)+nlgn 。

       T(n/b)= 2T(n/22)+(n/2)lg(n/2)。

       T((n/b2)= 2T(n/23)+ (n/22)lg(n/22)。

       ……

       于是得到：T(n)= nlgn+(nlgn-lg2)+ (nlgn-2lg2)+ (nlgn-22lg2)+···+(nlgn-2hlg2)，h=lgn。

       根据等差、等比数列求和公式化简有：

       T(n)=n(lgn)2 –(n-1)lg2，所以T(n)= O( n(lgn)2)，而不是O( nlgn)。

       通过这个例子可以看出，当f(n)不是多项式的时候计算就有可能变得比较复杂，甚至无法计算。但是通过Master定理以及具体的数学变换技巧在某些情况下还是可行的。

       综上所述，可以得出以下结论：在针对形如T(n)=aT(n/b)+f(n)的递归方程求解方法里，使用递归树是一种比较可行的通用办法。

=======================================================

T(n)=2T(n/2)+n=o(nlogn)

大o记号：大O符号（Big O notation）是用于描述函数渐进行为的数学符号。更确切地说，它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界（百度百科）

T(n)=2T(n/2)+n

设n=2^k
T(n/2)=2T(n/2^2)+n/2
T(n/2^2)=2T(n/2^3)+n/2^2
T(n)=2T(n/2)+n=2^2T(n/2^2)+2*n/2+n=2^3T(n/2^3)+2^2*n/2^2+2*n/2+n
    =2^kT(1)+kn=nT(1)+kn=n(logn+T(1))=o(nlogn)

注：T(1)是常数，可以忽略 

https://blog.csdn.net/yuyajun06/article/details/79791508?utm_source=copy 

https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)

相关知识

递归算法的时间复杂度分析
编程求n
探究n阶常系数线性非齐次方程L[y]=e~(ax)的公式解
求证：当1≤n≤4，n∈N*时，f（n）=（2n+7）·3n+9能被36整除。
公式F=ma中的力从哪来？
递归函数
设含有 m个方程的n元非齐次线性方程组为Ax=b且R(A)=r, 则( )
在不计机械重、绳重、部件间摩擦时，F1=（）N，F2=（）N。比较F1、F2...
ACM之while(scanf(“%d”,&n)!=EOF)
求组合c(n,m)的简单算法 （新手篇04）

网址: 递归方程T(n)=aT(n/b)+f(n)之通用解法 https://www.mcbbbk.com/newsview522648.html