complexity-theory - Divide et impera 用于矩阵旋转

Question

我试图从这个练习中解决第二个问题 b 和 d 子问题：http: //courses.engr.illinois.edu/cs473/sp2010/homework/hw1.pdf

我通过以下方式解决了b：

我的第一个问题是：我的解决方案对问题 2/b 是否正确？我的第二个问题是：我应该在问题 2/d 中做什么？这对我来说有点奇怪。

感谢您的时间和帮助。

Answer 1

从阅读问题的第二段来看，在我看来，你的答案对于第 2b 部分是不正确的。我的阅读是 2^n 旋转需要 5 个 2^(n-1) 块。如果这是正确的，那么你的方程应该是

B(2^n) = 5 * B(2^(n-1)) = 25 * B(2^(n-2)) = ... = 5^n * B(1)

其中 B(x) 是 x 的 blit 数。（很抱歉不知道如何做花哨的方程式。）

对于 2d，我读它的意思是 B(2^n) 的时间复杂度是多少。试一试，让我们看看结果如何。

让我知道你的想法。