递归方程求解

来自计算思维百科
跳转至: 导航搜索

从递归算法的时间复杂度分析可知,递归算法、分治算法的时间复杂度常表示为递归方程形式。那么,如何求解该方程得到算法的时间复杂度?

解递归方程最常用的方法是递推。所谓递推是从原始递归方程开始,将方程右边出现的未知函数T不断用递归方程代入,直到右边不再含未知函数T,然后将所得结果进行化简。

例子

解递归方程:RTENOTITLE

解 T(n)=T(n-1)+n-1

          =T(n-2)+n-2+n-1

           =…

         =T(1)+1+2+…+n-1

          =n(n-1)/2

分析二分查找的时间复杂度

解 假设在n个元素中查找e的时间为T(n)。根据算法,当n=1时,只需一次比较T(1)=1;当n>1时,与中间值比较后,数据折半,在余下数据中查找,T(n)=T(n/2)+1。

  因此,二分查找时间复杂度的递归方程为:

                            RTENOTITLE

用递推法求解得:

           RTENOTITLE

二分查找的时间复杂度为Θ(log2n)。

递推方法一般适用于一阶递归方程。对于二阶以上,T(n)依赖于它前面更多项,直接递推将导致递推后的项太多,从而使得求和公式过于复杂,因此需要先把递归方程化简,然后再进行迭代。使用差消法可以将某些高阶递归方程化简为一阶递归方程。

解递归方程:RTENOTITLE

由原方程得到:

           RTENOTITLE

          RTENOTITLE

两式相减得:

         nT(n)-(n-1)T(n-1)=2T(n-1)+2n-2

化简得:

         nT(n)=(n+1)T(n-1)+2n-2

变形并递推得:

         RTENOTITLE

其中,右边第一式为调和级数,

                     RTENOTITLE    

右边第二式:

                     RTENOTITLE

因此得,T(n)=Θ(nlogn)。

主定理(MasterTheorem)

设a≥1,b>1为常数,f(n)为函数,T(n)为非负整数,且

T(n)=aT(n/b)+f(n)

则有以下结果:

  1. 若f(n)=O(nlogba-ε),ε<0,那么T(n)=Θ(nlogba)
  2. 若f(n)=Θ(nlogba),那么T(n)=Θ(nlogbalogn)
  3. 若f(n)=Ω(nlogba+ε),ε>0,且对于某个常数c和所有充分大的n有af(n/b)≤cf(n)

 那么T(n)=Θ(f(n))