数学归纳法证明时间复杂度
1. T(n)=1+∑j=0n−1T(j)
欲证明 T(n)=2n（为了简化问题的方便，这里忽略了问题的背景信息，边界条件：T(0)=1）。
已知边界条件：T(0)=20=1，由数学归纳法，化结论为条件，则有：
T(n)====1+∑j=0n−1T(j)1+∑j=0n−12j1+20+21+…+2n−11+20(1−2n)1−2=2n
版权声明：本文为mtcnn原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
欲证明 T(n)=2n（为了简化问题的方便，这里忽略了问题的背景信息，边界条件：T(0)=1）。
已知边界条件：T(0)=20=1，由数学归纳法，化结论为条件，则有：