数学归纳法证明时间复杂度 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