王晓东的数据结构与算法分析18页有个问题不懂。。。
书上题目：我们要估计T（n）的上界，T（n）满足递归方程：T（n）=2T([n/2])+n，其中[]是地板函数的记号。
我们推测T（n）=0(n),即推测存在正的常数C和自然数no;使得当n >= no时有：
T（n）<=Cn,
事实上取no = 2~2 = 4, C=(T(n)/n)+1;
那么当no <= n <= 2no时，T（n）<=Cn成立。
假设2~（k-1）no <= n <= 2~(k)no, k>=1时，T（n）<=Cn成立。
那么，当2~（k）no <= n <= 2~(k+1)no时：
则T(n) = 2T([n/2])+n <= 2C[n/2] + n < 2C * n/2 + n <= c*n+n = (c+1)n = 0(n)
书上说这样的证明有问题：原因是它滥用了记号0，错把（c+1）n与 cn等同起来。。。。不理解。。
我认为应该是等同的，
因为：上界的定义是：存在正的常数C和自然数No，使得当N>No时有F(n)<=Cg(n)则称函数F(n）当N充分大时有界，g(n)是它的一个上界，记为F(n)=O(g(n)).
定义里的C不是固定的，那么C和C+1应该是可以等同的。
我的理解错在哪里了。。。。求高手。。。
[解决办法]
C必须是一致，就是说不同的N用的是同一个C。C不能跟着N而变。
它这里扩大了2倍就必须把C变成C+1，这就不符合刚才说的C不能跟着N而变了。
事实上这个T不是线性的而是nlogn。
[解决办法]
对这个是nlogn的，T[n]=2T[n/2]+n=4T[n/4]+n+n=...=nlogn
