矩阵旋转的除等序法

Question

我已经尝试解决本练习中的第二个问题b和d子问题：http://courses.engr.illinois.edu/cs473/sp2010/homework/hw1.pdf

我用下面的方法解出了b：

​

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

感谢您的时间和帮助。

Answer 1

从问题的第二段看，我觉得你对第2b部分的回答不正确。我的解读是，2^n的旋转需要2^(n-1)的5个blits。如果这是正确的，那么你的方程式应该是

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

其中B( x )是x的blits数。(抱歉，我不知道如何计算奇特的方程。)

对于2d，我把它理解为B(2^n)的时间复杂度是多少。试一试，让我们看看会有什么结果。

让我知道你的想法。