文章目录
  1. 1. 代换法
  2. 2. 递归树法
  3. 3. 主方法 (master method)
  4. 4. 差分方程法(Difference Formula Method)
  5. 5. 实例

今天遇到一个问题,求递归程序 F(n) = F(n-1)+F(n-3)+F(n-5) 的时间复杂度(省去了不重要的部分)。想了很久没搞定,决定晚上来整理一下递归算法时间复杂度的求法。

比较常见的方法有以下几种:

代换法

基本步骤是先推测递归方程的显式解,然后用数学归纳法来验证该解是否合理

T(n) = 4T(n/2) + O(n),其中T(1) = O(1),我们猜测一个解T(n) = O(n2 )。

递归树法

某算法的计算时间为:T(n) = 3T(n/4) + O(n),其中T(1) = O(1),迭代两次可将右端展开为:

T(n) = 3T(n/4) + O(n)
     = O(n) + 3( O(n/4) + 3T(n/42 ) )
     = O(n) + 3( O(n/4) + 3( O(n/42 ) + 3T(n/43 ) ) )

从上式可以看出,这是一个递归方程,我们可以写出迭代i次后的方程:

T(n) = O(n) + 3( O(n/4) + 3( O(n/42 ) + ... + 3( n/4i + 3T(n/4i+1 ) ) ) )

当n/4i+1 =1时,T(n/4i+1 )=1,则

T(n) = n + (3/4) + (32 /42 )n + ... + (3i /4i )n + (3i+1 )T(1)
     < 4n + 3i+1

而由n/4i+1 =1可知,i<log4 n,从而

3i+13log4 n+1 = 3log3 n*log4 3 +1 = 3nlog4 3

代入得:

T(n) < 4n + 3nlog4 3,即T(n) = O(n)

主方法 (master method)

该方法仅适用于特定格式的递归式

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

其中,a≥1和b≥1,均为常数,f(n)是一个确定的正函数。在f(n)的三类情况下,我们有T(n)的渐近估计式:

  1. 若对于某常数ε>0,有f(n) = O(nlogb a-ε ),则T(n) = O(nlogb a )
  2. 若f(n) = O(nlogb a ),则T(n) = O(nlogb a *logn)
  3. 若f(n) = O(nlogb a+ε ),且对于某常数c>1和所有充分大的正整数n,有af(n/b)≤cf(n),则T(n)=O(f(n))。

例如:

T(n)=4T(n/2)+n , 则a=4,b=2,f(n)=n,计算nlog(b,a)=n2>f(n), 满足模式一,因此T(n) = nlog(b,a)=O(n2)

T(n)=4T(n/2)+n2,则根据上面计算,满足模式二,因此T(n)=O(n2logn)

T(n)=4T(n/2)+n3,满足模式三,T(n)=O(n3)

差分方程法(Difference Formula Method)

可以将某些递归方程看成差分方程,通过解差分方程的方法来解递归方程,然后对解作出渐近阶估计。

实例

  1. 斐波那契数列递归方法

    T(n)=o(〖((1+√5)/2 )〗^n)
    
文章目录
  1. 1. 代换法
  2. 2. 递归树法
  3. 3. 主方法 (master method)
  4. 4. 差分方程法(Difference Formula Method)
  5. 5. 实例