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

Question

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

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

对于 Strassen 的方法。

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

我是怎么理解的，的系数(naive 为 8，Strassen 为 7)是每一层引入的递归次数，或者说子问题的增长率。除数是减少问题的因素。 加数是每个特定循环节点的运行时间。

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

下面是我从 GeeksforGeeks 获得的朴素方法的图片:

Answer 1

来自 Introduction to Algorithms, 3^rd Edition ，页。 77:

Let T(n) be the time to multiply two n x n matrices using this [the naive matrix multiplication] procedure.

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