书中讲并归算法的时间复杂度数学分析:
C(N)表示比较次数, 当N为2的幂(N=2^n)时, 那么:
C(N) = C(2^n) = C(2^n) = 2C(2^(n-1))+2^n ;
两边同时除以2^n, 得到 C(2^n)/2^n = C(2^(n-1))/2^(n-1)+1 ;
然后将这个公式替换成右边的一项, 可得: C(2^n)/2^n = C(2^(n-2))/2^(n-2)+1+1 ;
将上一步骤重复n-1次,得到C(2^n)/2^n = C(2^0)/2^0+n, 带入n=logN得到:
C(N)=NlogN.
我对于“然后将这个公式替换成右边的一项, 可得: C(2^n)/2^n = C(2^(n-2))/2^(n-2)+1+1 ;”这一步看了好久都没看明白，这里是怎么变化的？
把C(2^n)/2^n = C(2^(n-1))/2^(n-1)+1里边的n换成n-1，然后把结果C(2^(n-1))/2^(n-1)=xxx替换原等式的右边就出来了。