1

我知道我的朴素矩阵乘法算法的时间复杂度为 O(N^3)...但是我如何通过我的值表证明这一点？大小是矩阵的行或列长度。对于完整的矩阵大小，请平方。

  • 尺寸 = 100 垫。多。经过时间：0.0199 秒。

    尺寸 = 200 垫。多。经过时间：0.0443 秒。

    尺寸 = 300 垫。多。经过时间：0.0984 秒。

    尺寸 = 400 垫。多。经过时间：0.2704 秒。

    尺寸 = 800 垫。多。经过时间：6.393 秒。

这就像查看值表并估计函数图......这些数字和 N^3 之间必须存在某种关系。我怎么理解它呢？

我在下面提供了我的算法。通过计算循环，我已经知道它是 O(N^3) 。我怎么能把它和我上面的值表联系起来呢？

 /**
* This function multiplies two matrices and returns the product matrix.
* 
* @param mat1
*           The first multiplier matrix.
* @param mat2
*           The second multiplicand matrix.
* @return The product matrix.
*/
private static double[][] MatMult(double[][] mat1, double[][] mat2) {
  int m1RowLimit = mat1.length, m2ColumnLimit = mat2[0].length, innerLimit = mat1[0].length;
  if ((mat1[0].length != mat2.length))
     return null;
  int m1Row = 0, m1Column = 0, m2Row = 0, m2Column = 0;
  double[][] mat3 = new double[m1RowLimit][m2ColumnLimit];
  while (m1Row < m1RowLimit) {
     m2Column = 0;
     while (m2Column < m2ColumnLimit) {
        double value = 0;
        m1Column = 0;
        m2Row = 0;
        while (m1Column < innerLimit) {
           value += mat1[m1Row][m1Column] * mat2[m2Row][m2Column];
           m1Column++;
           m2Row++;
        }
        mat3[m1Row][m2Column] = value;
        m2Column++;
     }
     m1Row++;
  }
  return mat3;
}
4

3 回答 3

2

方法论

好的。所以你想证明你的算法的时间复杂度是O(n^3). 我理解您为什么要查看程序运行计算所需的时间，但这些数据并不可靠。我们所做的是，我们应用一种奇怪形式的限制来抽象出算法的其他方面，并将我们的metric.

指标

Ametric是我们将用来衡量你的算法的。它是发生最多或承担最大处理权重的操作。在这种情况下，它是这一行：

value += mat1[m1Row][m1Column] * mat2[m2Row][m2Column];

推导递归关系

据我了解，下一步是从您的算法中得出递归关系。也就是说，根据过去的功能描述您的算法如何运行。让我们看看你的程序是如何运行的。

正如您所解释的，您已经查看了三个 while 循环，并确定程序是有序的O(n^3)。不幸的是，这不是数学上的。这只是似乎经常发生的事情。首先，让我们看一些数字示例。

当 时m1RowLimit = 4, m2ColumnLimit = 4, innerLimit = 4，我们的指标是运行4 * 4 * 4 = 4^3次数。

当 时m1RowLimit = 5, m2ColumnLimit = 5, innerLimit = 5，我们的指标是运行5 * 5 * 5 = 5^3次数。

那么我们如何在递归关系中表达这一点呢？好吧，使用一些基本的数学，我们得到：

T(n) = T(n-1) + 3(n-1)^2 + 3(n-1) + 1 for all n >= 1
T(1) = 1

使用正向替换和数学归纳法求解递归关系

现在，是我们使用一些前向替换的地方。我们首先要做的是了解这种关系（这也测试它是否准确）。

T(2) = T(1) + 3(1^2) + 3(1) + 1 = 1 + 3 + 3 + 1 = 8.
T(3) = T(2) + 3(2^2) + 3(2) + 1 = 8 + 12 + 6 + 1 = 27
T(4) = T(3) + 3(3^2) + 3(3) + 1 = 27 + 27 + 9 + 1 = 64

现在，我们断言 T(n) = n^3 的假设。让我们测试一下基本情况：

T(1) = 1^3 = 1. // Correct!

现在我们使用数学归纳法对其进行下一步测试。算法每次加1，所以下一步是：T(n+1). 那么我们需要证明什么呢？好吧，我们需要证明，通过在一侧增加n1，在另一侧发生相同的效果n。如果它对 all 是真的n + 1，那么它对n + 1 + 1等等都是真的。这意味着，我们的目标是证明：

T(n + 1) = (n + 1)^3

T(n + 1) = T(n - 1 + 1) + 3(n + 1 - 1)^2 + 3(n + 1 - 1) + 1
         = T(n) + 3(n)^2 + 3(n) + 1
Assume T(n) = n^3
T(n + 1) = n^3 + 3(n)^2 + 3(n) + 1
T(n + 1) = (n+1)^3 // Factorize the function.

所以此时，您已经证明您的算法的运行时间复杂度为O(n^3).

于 2013-05-01T23:14:43.853 回答
2

第一个响应涵盖了如何很好地证明算法的时间复杂度。

但是，您似乎在问如何将基准测试的实验结果与时间复杂度联系起来，而不是如何证明时间复杂度。

那么，我们如何解读实验数据呢？好吧，您可以从简单地绘制数据开始（y 轴上的运行时间，x 轴上的大小）。有了足够的数据点，这可以为您提供有关算法行为的一些提示。

由于您已经知道算法的预期时间复杂度，因此您可以绘制“最佳拟合曲线”（即最适合您的数据的形状为 n^3 的线）。如果您的数据与该行匹配得相当好，那么您可能是正确的。如果不是，则可能是您犯了一些错误，或者由于您没有考虑到的因素，您的实验结果不匹配。

要确定最佳拟合 n^3 线的方程，您可以简单地取计算出的时间复杂度，将其表示为方程，然后猜测未知数的值，直到找到适合的方程。因此，对于 n^3，您将拥有：

t = a*n^3 + b*n^2 + c*n + d

找出形成最适合您的数据的方程的 a、b、c 和 d 的值。如果那个合身仍然不够好，那么你就有问题了。

对于更严格的技术，您必须询问更精通统计学的人。我相信你想要计算的值是决定系数（又名 R^2，基本上告诉你预期结果和实际结果之间的差异）。然而，就其本身而言，这个价值并不能证明很多。这个验证变量之间假设关系的问题被称为回归模型验证；如果 R^2 不足以满足您的目的，则维基百科文章提供了有关如何进一步使用此功能的更多信息。

于 2013-05-02T00:10:07.617 回答
2

根据经验，您可以使用相邻的三次多项式趋势线绘制数据以供参考。

excel图表

CSV 数据：

100, 0.0199
200, 0.0443
300, 0.0984
400, 0.2704
800, 6.393
于 2013-05-02T00:39:45.333 回答