为什么在方阵乘法的递归中输入大小除以2而不是4？

Question

在分析方阵乘法运行时，我了解到运行时是

对于朴素的分而治之的方法，和

对于施特拉森的方法。

为什么 N 除以 2 而不是 4？

我怎么理解，系数 （8 表示 naive，7 表示 Strassen）是每个级别引入的递归次数，或者子问题的增长率。除数是减少问题的因子。这 addend 是每个特定重复节点的运行时间。

如果朴素算法和施特拉森方法都将输出矩阵划分为 矩阵在哪里 是行数和列数，问题是不是减少了 4 倍而不是 2 倍，因为在每个级别我们都在解决 4 个较小矩阵的问题？

下面是我从 GeeksforGeeks 获得的天真方法的图像：

Answer 1

摘自《算法导论》，第 3^版，第 14 页。77：

令 T(n) 为使用此[朴素矩阵乘法]过程将两个 nxn 矩阵相乘的时间。

n 不是任何一个矩阵中元素的数量，它是一个维度。因此，由于矩阵维度被递归地分成两半，因此除数是 2 而不是 4。