og(n)
下限很好证明，取n=2^k即可。
上限是log(n)要一些技巧。假设T是以上函数的复杂度，那么递推式是T(2k)=T(k)+1, T(2k+1)=T(k)+T(k+1)+3。
当k=2t的时候，T(2k+1)=2T(t)+T(t+1)+7。当k=2t+1的时候，T(2k+1)=T(t)+2T(t+1)+7。
令S(n)=max(T(1),...,T(n))。那么可以通过归纳法证明3S(t+1)+7 >= S(2k+1)。而对于偶数，3S(t+1)+7 >= S(2k)显然成立。这样的话S就满足一个下面的一个形式：S(n)<=3*S(ceil(n/4)) + 7。这样的话直接有S(n) = O(log(n)/log(3/4))=O(logn)。由于T(n)<=S(n)，T(n)=O(logn)
顺便log(n)/log(3/4)是一个S(n)的一个挺精确的估计。
|
楼主
