java - 如何从值表中估算时间复杂度？

Question

我知道我的朴素矩阵乘法算法的时间复杂度为 O(N^3)... 但是我怎样才能通过我的值(value)表来证明这一点呢？大小是矩阵的行或列长度。对整个矩阵大小进行平方。

• 大小 = 100多。耗时:0.0199 秒。

  尺寸 = 200 垫。多。耗时:0.0443 秒。

  尺寸 = 300 垫。多。耗时:0.0984 秒。

  尺寸 = 400 垫。多。耗时:0.2704 秒。

  尺寸 = 800 垫。多。耗时:6.393 秒。

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

我在下面提供了我的算法。我已经通过计算循环数知道它是 O(N^3)。我怎样才能将它与我上面的值(value)表联系起来呢？

 /**
* 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;
}

Answer 1

方法论

---

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

指标

---

metric 是我们将用来衡量您的算法的指标。它是发生次数最多或处理权重最大的操作。在这种情况下，就是这一行:

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

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

---

现在，是我们使用一些 forward substitution 的地方.我们首先要做的是感受一下这种关系(这也会测试它是否准确)。

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)。那么我们需要证明什么呢？我们需要证明，通过在一侧将 n 增加 1，另一侧的 n 也会产生相同的效果。如果它对所有 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)。