时间复杂度分析 递归关系
四种求解方法
置换法(Substitution )
Make a guess and verify it(假设-论证).
The three steps of the substitution method:
( 置换法的三步骤 )
1. Make a good guess( 猜想 )
2. Verify the guess, assuming that it can be verified
for some base case n = n 0
( 验证猜想对于 n = n 0 的正确性 )
3. Choose an n 0 for which the guess works and such
that Step 2 for any n > n 0 does not depend on the
claim for some n' < n 0
( 验证猜想对于 n > n 0 的正确性 )
Changing Variables (更换变元)
Use algebraic manipulation to turn an
unknown recurrence into one similar to what
you have seen before. (通过数学变化,将陌生的
迭代关系转变为熟悉的形式)
Example: T(n) = 2T(n^1/2 ) + lg n
Rename m = lg n and we have
T(2^m ) = 2T(2^m/2 ) + m
Set S(m) = T(2 m ) and we have
S(m) = 2S(m/2) + m => S(m) = O(m lg m)
Changing back from S(m) to T(n), we have
T(n)=T(2^m )=S(m)= O(m lg m) = O(lg n lg lg n)
Allows us to arrive at a guess(帮助猜想).
The guess can then be verified using the
substitution method(置换法论证).
迭代法(Iteration )
Provides solutions to recurrences of a quite
restricted, but very common, nature(定理化).
k=logb(n) n=b^k