小弟是想跨考资工的初学者 对于某些算法不慎明白
以下这题小弟困惑了许久 最后还是决定在板上问了
Solving the recurrence T(n)=2T(floor(sqrt(n)))+lgn
我照着洪杰的方法解
猜 T(n)=O(lgn*lglgn)
假设T(floor(sqrt(n)))<=c*lg(sqrt(n))*lglg(squt(n))成立
则
T(n)=2T(floor(sqrt(n)))+lgn
<=2*c*lg(sqrt(n))*lglg(sqrt(n))+lg2
=2*c*(1/2)*lgn*lg((1/2)*n)+lgn
=lgn(c*lglgn-c+1)
所以当c>=1时此式会成立
但是他再找boundary condition时
他取当 c=1 n0=1
T(n)<=lgn(clglgn-c+1)<=clgnlglgn 此式成立
但是我的问题是 当n0=1时
lglgn=lglg1=lg0
这样这个式子不就没有意义了吗 为什么还会成立?
然后我发现好像很多人在解substitution method时
都不会去证明boundary condition
是因为证明那些东西太琐碎了
所以研究所考试的时候不会扣分吗?