Posted on 2010-05-20 11:11
千張 閱讀(1574)
評論(0) 編輯 收藏 引用 所屬分類:
程序員筆試寶典
對于T(n) = a*T(n/b)+c*n^k;T(1) = c 這樣的遞歸關系，有這樣的結論：
if (a > b^k) T(n) = O(n^(logb(a)));logb(a)b為底a的對數
if (a = b^k) T(n) = O(n^k*logn);
if (a < b^k) T(n) = O(n^k);
T(n) = 25T(n/5)+n^2 = 25(25T(n/25)+n^2/25)+n^2
= 625T(n/25)+n^2+n^2 = 625T(n/25) + 2n^2
= 25^2 * T( n/ ( 5^2 ) ) + 2 * n*n
= 625(25T(n/125)+n^2/625) + 2n^2
= 625*25*T(n/125) + 3n^2
= 25^3 * T( n/ ( 5^3 ) ) + 3 * n*n
= ....
= 25 ^ x * T( n / 5^x ) + x * n^2
T(n) = 25T(n/5)+n^2
T(0) = 25T(0) + n^2 ==> T(0) = 0
T(1) = 25T(0)+n^2 ==> T(1) = 1
x = lg 5 n
25 ^ x * T( n / 5^x ) + x * n^2
= n^2 * 1 + lg 5 n * n^2
= n^2*(lgn)