算法导论中的一个疑惑
算法导论英文第三版87页，关于归纳证明算法边界的问题，有一点不明白，望高人指点！
Sometimes, a little algebraic manipulation can make an unknown recurrence similar
to one you have seen before. As an example, consider the recurrence
T(n）=2T([n^1/2])+lg(n);
which looks difficult. We can simplify this recurrence, though, with a change of
variables. For convenience, we shall not worry about rounding off values, such
as n^1/2(根号n), to be integers. Renaming m = lg(n) yields
T(2^m) =2T(2^m/2)+m
We can now rename S(m)=T(2^m)to produce the new recurrence
S(m) = 2S(m/2) + m ; // 替代后m应该变为lgm吧，为什么还是m?
which is very much like recurrence (4.19). Indeed, this new recurrence has the
same solution: S(m)=O(m×lgm). Changing back from S(m)to T(n), we obtain
T(n)=T(2^m)=S(m)=O(m*lgm)= O(lgn*lglg n)
[解决办法]
你说的是哪一章，哪一段。我的是第四版。
[解决办法]
m没有变啊。只是把T(2^m)用S(m)代进去了而已
[解决办法]
S(m)=T(2^m)，设的是这个因变量。不是自变量！
T(2^m) =2T(2^m/2)+m
S(m) = 2S(m/2) + m
你自己想想吧。
例如：若他不是递归的呢就很好理解了。
若：T(2^m) = m;
S(m)=T(2^m);
那么，S(m) 等于多少呢？肯定是 m啊。
[解决办法]
