0
私が学んだことから、ボトムアップの複雑さはn^3でなければなりません。しかし、私はそれがO（n）に似ていることを示しています。私は何度もこれらのコードをチェックしてきましたが、なぜそれがn^3の複雑さではないのかという手がかりはまだありません。ここで何かが恋しい？なぜボトムの複雑さはO（n^3）でないのですか
/**
* Using the bottom-up approach to fill in the table m and s for matrices P
* @param P an array storing the matrices chain
*/
public void matrixChainOrder(int[] P){
int n = P.length-1;
m = new int[n+1][n+1];
s = new int[n][n+1];
for (int i=1; i <= n; i++){
m[i][i] = 0;
}
for (int l = 2; l <= n; l++){
for (int i = 1; i <= n-l + 1; i++){
int j = i + l - 1;
m[i][j] = Integer.MAX_VALUE;
for (int k = i; k <= j -1; k++){
int q = m[i][k] + m[k+1][j] + P[i-1]*P[k]*P[j];
if (q < m[i][j]){
m[i][j] = q;
s[i][j] = k;
}
}
}
}
}
/**
* Print out the optimal parenthesization of matrices chain P
* @param s the auxiliary table storing the parenthesization
* @param i the index of the start matrix
* @param j the index of the end matrix
*/
public void printOptimalParens(int[][] s, int i, int j){
if (i == j){
System.out.print("A"+ i);
}
else{
System.out.print("(");
printOptimalParens(s, i, s[i][j]);
printOptimalParens(s, s[i][j] + 1, j);
System.out.print(")");
}
}
/**
* Compute the product of the matrices chain
* @param A The matrices chain, it is an array of matrices
* @param s the auxiliary table storing the parenthesization
* @param i the start matrix
* @param j the end matrix
* @return the product matrix of the matrices chain
*/
public long[][] matrixChainMultiply(long[][][] A, int[][] s, int i, int j){
if (i == j){
return A[i];
}
if (i + 1 == j){
return multiply(A[i], A[j]);
}
long[][] C = matrixChainMultiply(A, s, i, s[i+1][j+1]-1);
long[][] D = matrixChainMultiply(A, s, s[i+1][j+1], j);
return multiply(C, D);
}
/**
* A helper method to compute 2 matrices
* @param X the first matrix
* @param Y the secodn matrix
* @return the product of these two matrices
*/
public long[][] multiply(long[][] X, long[][] Y){
int r = X.length;
int c = X[0].length;
int c2 = Y[0].length;
long[][] B = new long[r][c2];
for (int u = 0; u < r; u++){
for (int v = 0; v < c2; v++){
for (int w = 0; w < c; w++){
B[u][v] += X[u][w] * Y[w][v];
}
}
}
return B;
}
あなたのアルゴリズムがO（n）であると信じている理由を説明しても良いと思います。 – justhalf
テストドライバーを書いた結果、O（n）とほぼ同じです。 – Mocao
試したn（チェーンの長さ）の値は何ですか？ – justhalf