0
從我所學到的，自下而上的複雜度應該是n^3，但是，我的結果顯示它幾乎就像O（n）。我一直在檢查這些代碼很多次，但仍然不知道爲什麼它不是複雜性。我在這裏想念什麼？爲什麼我的底部複雜度不是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