1

私の単純な行列乗算アルゴリズムの時間の複雑さは O(N^3) であることはわかっています... しかし、値の表を使用してそれを証明するにはどうすればよいでしょうか? サイズは、行列の行または列の長さです。完全なマトリックスサイズの場合は2乗します。

  • サイズ = 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

最初の回答は、アルゴリズムの時間の複雑さを十分に証明する方法をカバーしています。

ただし、時間の複雑さを証明する方法ではなく、ベンチマークの実験結果を時間の複雑さと関連付ける方法を尋ねているようです。

では、実験データをどのように解釈すればよいでしょうか。データを単純にプロットすることから始めることができます (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

方法論

わかった。したがって、アルゴリズムの時間計算量が であることを証明したいとしますO(n^3)。プログラムが計算を実行するのにかかる時間を見る理由は理解できますが、このデータは信頼できません。私たちがしていることは、奇妙な形式の制限を適用して、アルゴリズムの他の側面から離れて抽象化し、metric.

メトリック

Ametricは、アルゴリズムを測定するために使用するものです。これは、最も発生する操作、または処理の重みが最も大きい操作です。この場合、次の行です。

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

再帰関係の導出

次のステップは、私が理解しているように、アルゴリズムから再帰関係を導出することです。つまり、過去の機能に基づいてアルゴリズムがどのように機能するかの説明です。プログラムがどのように実行されるかを見てみましょう。

あなたが説明したように、あなたは 3 つの 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)です。では、何を証明する必要があるのでしょうか? 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)。

于 2013-05-01T23:14:43.853 に答える