我可以通过证明它只需要 5 次乘法来证明 2 * 2 的矩阵 A 的平方是 O(n^log5)。到现在为止我没有问题，但是当我想解释为什么我们不能将它推广到其他平方情况（不同的 n*n 大小）的两个原因之后，我可以想出一个如下：
我能想出的第一个原因是我将例如 3*3 矩阵与自身相乘并得出结论，它至少有 6 次乘法，因此它的运行时间至少为 O(n^log6)，其中 n^epsalon 大于 O( n^log5) 所以它比较慢，我们不能将 O(n^log5) 推广到所有情况。现在我需要另一个原因，但我不知道如何解释第二个原因有人可以帮忙吗（我只需要一个提示就可以提出一个想法）？
您不可能从示例中得出大 O 表示法的运行时间。Big-O 表示法告诉我们算法的复杂性如何随着参数的增加（在本例中为矩阵大小 n）而扩展，所以如果你真的想通过实验来近似它，你至少必须计算几个测试大小的运行时间.
但我怀疑你能否找到手动平方 100x100 矩阵的最佳方法……这实际上是一个难题。我们可以肯定的是，它并不比矩阵-矩阵-积复杂。对于那些我们有一个 Omega(n^2) 的下限，因为我们必须至少查看矩阵的每个条目一次。我们有一个大约为 O(n^2.3729) 的（理论上的）完美算法的上限，因为有一种已知的算法具有这种复杂性。（见http://en.wikipedia.org/wiki/Matrix_multiplication#Algorithms_for_efficient_matrix_multiplication）
顺便说一句 2.3729 < log6 您建议的最小值 - 这与以下声明并不矛盾，您可能需要 6 次乘法来处理 3x3 矩阵，因为再次：O 表示法只关心运行时间的渐近行为，因为 n 变大- 而不是关于个人 n 的任何特定运行时间。