问Big-O算法分析

EN

如果你在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因素。尝试使用他们的提示，这应该是好的。

3.5和3.6之间的区别是T(n/4)中的ceil和floor函数。除此之外，它们是相同的。据我所知，差异对O(T(n))的计算并不重要，正如您可以从预期结果中看到的那样。

我希望这能帮到你。