问题: alt text http://img12.imageshack.us/img12/2706/image2ot.jpg
我做了什么: alt text http://img29.imageshack.us/img29/9192/image3sc.jpg
但我完全不知道 3.5 和 3.6 之间的区别。
最佳答案
如果您对 3.5 的解决方案更加谨慎，差异就会更加明显。你的第一行
T(n) <= n/4 (lg n)/4 + 3n/4 (3 lg n)/4 + n
不太对。首先，归纳假设是存在一个常数C这样
T(n) <= C n log n
所以你可能应该保留那个 C大约。其次，您将跳过删除 floor 函数的步骤。您真正知道的是(为简单起见忽略常量 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周围的因素。尝试使用他们的提示，应该没问题。
关于algorithm - 大O算法分析，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1586189/