先考虑简化的情形

　　T(2n)=2T(n)+1=>T(2n)+1=2(T(n)+1)

　　这样当n=2^k时就转化到等比数列

　　T(2^k)+1=C*2^k,即T(n)=Cn-1,C是一个正常数

　　然后用归纳法证明不仅是2的幂,对一般的n上述结论也成立

　　如果只需要大O记号的话T(n)=O(n)

　　当然,对于很多算法复杂度分析,没必要如此细致,对n=2^k讨论完之后只要再证明T(n)单调也就足够了