问题: 替代文字http://img12.imageshack.us/img12/2706/image2ot.jpg
我做了什么: 替代文字http://img29.imageshack.us/img29/9192/image3sc.jpg
但我完全不知道3.5和3.6之间的区别.
Jes*_*der 10
如果你在3.5的解决方案中更加小心,差异将更加清晰.你的第一行
T(n) <= n/4 (lg n)/4 + 3n/4 (3 lg n)/4 + n
是不对的.首先,归纳假设是存在C这样的常数
T(n) <= C n log n
所以你可能应该保持这种状态C.其次,您正在跳过删除楼层功能的步骤.你真正知道的是(C为了简单而忽略常数)
T(n) <= floor(n/4) lg (floor(n/4)) + floor(3n/4) lg (floor(3n/4)) + n
那你怎么照顾地板？好吧,floor(x) <= x; 但是lg(floor(x))(显示两次)呢？这里的关键是lg增加功能,所以lg(floor(x)) <= lg(x)也是如此.所以
T(n) <= n/4 lg(n/4) + 3n/4 lg(3n/4) + n
现在,随着对数的某些属性清理(你将需要使用提示有关lg 3),并完成你的感性的一步.
好的,知道这与3.6的区别是什么？那么,现在你有了天花板功能而不是地板功能,所以你不能忽略它.但
ceiling(x) <= x + 1
所以你可以类似地工作,还有一些额外的+ 1因素.尝试使用他们的提示,它应该没问题.