算法生成哈达玛矩阵的运行时间

Question

我想设计一个算法来使用分而治之的技术来生成哈达玛矩阵。为此，我决定使用四次递归调用来生成矩阵的每个项，然后继续每个步骤的递归调用，以减少一个值的Hadamard矩阵。例如，H（3）被分成4个H（2）项，其中一个为负数，等等直到H（0）。在制定出我与之结合的复发关系时

C(n) = 4C(n-1) + 1. 

但是，分而治之涉及输入的分割而不是减1？从概念上讲，我认为将一个矩阵分成更小的矩阵的子集可以作为分而治之。无论如何，我结束了4^n的运行时间。这对我设计的算法是否准确？

Answer 1

这是准确的。鉴于n的解释，最终矩阵是2^n -，其中4^n元素。涉及m甲复发，元件的数量，将是

T(m) = 4T(m/4) + 1, 

与一个解决方案，是O(m)。