最近菜雞作者苦于解遞歸方程求解時(shí)間復(fù)雜度的一些問題
整理一下思路
遞歸算法的運(yùn)行時(shí)間常用遞歸表達(dá)式表示嗡髓。
本文主要講解如何從遞歸表達(dá)式求解出時(shí)間復(fù)雜度挠唆。
萬變不離其宗偿枕，總結(jié)以下四種形式年局。
例一：
T(n) = T(n-1)+1
解：T(n) = T(n-1)+1 = [T(n-2)+1]+1 = T(n-2)+2 = T(n-3)+3 = ... = T(n-n)+n = n
故 O(n) = n
例二：
T(n) = T(n-1)+n-1
解：T(n) = T(n-1)+n-1 = T(n-2)+(n-2)+(n-1) = T(n-3)+(n-3)+(n-2)+(n-1) = ...
= T(n-(n-1))+n-(n-1)+...+(n-2)+(n-1) = 0+1+2+3+4+...+(n-1) = n(n-1)/2
故 O(n) = n^2
例三：
T(n) = 2T(n-1)+1
解：T(n) = 2T(n-1)+1 = 2( 2T(n-2)+1)+1 = 4T(n-2)+2+1 = ...
= 2(n-1)T(n-(n-1))+2(n-2)+...2^2+2+1 = 2(n-1)+2(n-2)+...22+2+1=2n-1
故O(n) = 2^n
例四：
T(n) = 2T(n/2)+n-1
解： T(n) = 2T(n/2)+n-1 = T(n) = 2(T(n) = 2T(n/4)+n/2-1)+n-1 = 4T(n/4)+2n-2-1 = 4(2T(n/8)+n/4-1)+2n-2-1
= 8T(n/8)+3n-4-2-1 = 2k(T(n/(2k)))+kn-2^(k-1)-...-4-2-1
令n=2^k
代入得：T(n) = (2k)T(1)+k(2k)-(2^(k-1)+...+4+2+1) = （k+1）(2k)-((2k)-1) = n(logn)+1
故 O(n)= n(logn)
