题目:
一个算法所需时间有下述递归方程表示,试求出该算法的时间复杂度的级别(或阶).
T(n) = 1 (若n=1)
T(n) = 2*T(n/2)+n (若n>1)
式中,n是问题的规模,为简单起见,设n是2的整数次幂.
分析过程:
由题目给出的递归方程,得到:
T(1)=1
T(2)=2*T(1)+2
T(4)=2*T(2)+4
T(8)=2*T(4)+8
T(16)=2*T(8)+16
......
T(2^m)=2*T((2^m)/2)+(2^m)
其中,m是整数(大于等于0),并且2^m=n
可以看到T(2^m)的等式里,不仅仅T((2^m)/2)是变动项,(2^m)也是变动项.
由于T(1)=1,是一个常数,先找出T(4)与T(1)之间的关系:
T(4)=T(2^2)=2*T(2)+4=2*(2*T(1)+2)+4
=(2^2)*T(1)+(2^2)+(2^2)=(2^2)*T(1)+2*(2^2)
再找出T(8)与T(1)之间的关系:
T(8)=T(2^3)=2*T(4)+8=2*((2^2)*T(1)+2*(2^2))+8
=(2^3)*T(1)+2*(2^3)+(2^3)=(2^3)*T(1)+3*(2^3)
也就是,有如下关系:
T(2)=T(2^1)=(2^1)*T(1)+1*(2^1)
T(4)=T(2^2)=(2^2)*T(1)+2*(2^2)
T(8)=T(2^3)=(2^3)*T(1)+3*(2^3)
根据上述等式,可以直接得出T(16)与T(1)的关系是:
T(16)=T(2^4)=(2^4)*T(1)+4*(2^4)
用题目给出的递归方程,验证一下T(16)与T(1)的关系:
T(16)=T(2^4)=2*T(8)+16=2*((2^3)*T(1)+3*(2^3))+16
=(2^4)*T(1)+3*(2^4)+(2^4)=(2^4)*T(1)+4*(2^4)
根据上述初步的等式关系,可以得出T(2^m)与T(1)的关系是:
T(2^m)=(2^m)*T(1)+m*(2^m)_____[公式1]
假设对于T(2^m),上述[公式1]成立,那么,我们要验证该公式是否也适用于T(2^(m+1)),
由题目给出的递归方程,得到:
T(2^(m+1))
=2*T(2^m)+(2^(m+1))
=2*((2^m)*T(1)+m*(2^m))+(2^(m+1))
=(2^(m+1))*T(1)+m*(2^(m+1))+(2^(m+1))
=(2^(m+1))*T(1)+(m+1)*(2^(m+1))
所以,对于T(2^(m+1)),[公式1]也成立.
因为T(1)=1,所以,[公式1]可以写成:T(2^m)=(2^m)+m*(2^m)
因为2^m=n,该等式两边取以2为底的对数,得到,log2(2^m)=log2(n),
也就是m=log2(n),将其填入公式T(2^m)=(2^m)+m*(2^m),得到:
T(2^m)
=T(n)
=(2^log2(n))+log2(n)*(2^log2(n))
=n+n*log2(n)
取最高阶项n*log2(n),
所以,该算法的时间复杂度是O(n*log2(n))
一个算法所需时间有下述递归方程表示,试求出该算法的时间复杂度的级别(或阶).
T(n) = 1 (若n=1)
T(n) = 2*T(n/2)+n (若n>1)
式中,n是问题的规模,为简单起见,设n是2的整数次幂.
分析过程:
由题目给出的递归方程,得到:
T(1)=1
T(2)=2*T(1)+2
T(4)=2*T(2)+4
T(8)=2*T(4)+8
T(16)=2*T(8)+16
......
T(2^m)=2*T((2^m)/2)+(2^m)
其中,m是整数(大于等于0),并且2^m=n
可以看到T(2^m)的等式里,不仅仅T((2^m)/2)是变动项,(2^m)也是变动项.
由于T(1)=1,是一个常数,先找出T(4)与T(1)之间的关系:
T(4)=T(2^2)=2*T(2)+4=2*(2*T(1)+2)+4
=(2^2)*T(1)+(2^2)+(2^2)=(2^2)*T(1)+2*(2^2)
再找出T(8)与T(1)之间的关系:
T(8)=T(2^3)=2*T(4)+8=2*((2^2)*T(1)+2*(2^2))+8
=(2^3)*T(1)+2*(2^3)+(2^3)=(2^3)*T(1)+3*(2^3)
也就是,有如下关系:
T(2)=T(2^1)=(2^1)*T(1)+1*(2^1)
T(4)=T(2^2)=(2^2)*T(1)+2*(2^2)
T(8)=T(2^3)=(2^3)*T(1)+3*(2^3)
根据上述等式,可以直接得出T(16)与T(1)的关系是:
T(16)=T(2^4)=(2^4)*T(1)+4*(2^4)
用题目给出的递归方程,验证一下T(16)与T(1)的关系:
T(16)=T(2^4)=2*T(8)+16=2*((2^3)*T(1)+3*(2^3))+16
=(2^4)*T(1)+3*(2^4)+(2^4)=(2^4)*T(1)+4*(2^4)
根据上述初步的等式关系,可以得出T(2^m)与T(1)的关系是:
T(2^m)=(2^m)*T(1)+m*(2^m)_____[公式1]
假设对于T(2^m),上述[公式1]成立,那么,我们要验证该公式是否也适用于T(2^(m+1)),
由题目给出的递归方程,得到:
T(2^(m+1))
=2*T(2^m)+(2^(m+1))
=2*((2^m)*T(1)+m*(2^m))+(2^(m+1))
=(2^(m+1))*T(1)+m*(2^(m+1))+(2^(m+1))
=(2^(m+1))*T(1)+(m+1)*(2^(m+1))
所以,对于T(2^(m+1)),[公式1]也成立.
因为T(1)=1,所以,[公式1]可以写成:T(2^m)=(2^m)+m*(2^m)
因为2^m=n,该等式两边取以2为底的对数,得到,log2(2^m)=log2(n),
也就是m=log2(n),将其填入公式T(2^m)=(2^m)+m*(2^m),得到:
T(2^m)
=T(n)
=(2^log2(n))+log2(n)*(2^log2(n))
=n+n*log2(n)
取最高阶项n*log2(n),
所以,该算法的时间复杂度是O(n*log2(n))