0

行列チェーン乗算問題の (非効率的な) 再帰手順は次のようになると思います (Cormen で与えられた再帰関係に基づく):

MATRIX-CHAIN(i,j)
    if i == j
        return 0
    if i < j
        q = INF

        for k = i to j-1
            q = min (q, MATRIX-CHAIN(i,k) + MATRIX-CHAIN(k+1, j) + c)  
            //c = cost of multiplying two sub-matrices.

        return q

このための時間計算量は次のようになります。

T(n) = summation over k varying from i to j [T(k) + T(n-k)]

ここで、n = 乗算する行列の数。

T(n) の値はどのようになりますか?

4

2 に答える 2

1

これはhttp://en.wikipedia.org/wiki/Catalan_numberです

漸化式は、括弧を使用していると見なすことができます。wikiページでは、数式に到達する方法について詳しく説明しています。

于 2012-08-28T12:20:05.650 に答える
0

これは役立つかもしれません：

各行列チェーンを 1 回計算する (そしてその値を保存する) だけで済みます。

start = i と j の間の任意の場所

end = start と j の間の任意の場所

k = 開始と終了の間の任意の場所

3 つの 1 (開始、k、終了を表す) 以外はすべて 0 の数字を考えると、

この特別な番号には j-i+1 桁があります。

たとえば、i = 3 で j = 6 の場合、4 桁の数字が必要で、次のオプションがあります。

1101 (i=3, k=4, j=6)

1011 (i=3, k=5, j=6)

0111 (i=4, k=5, j=6)

1110 (i=3, k=4, j=5)

i,j,k の選択肢の数 = Combinations(3, j-i+1)

これはn!/(k! * (n-k)!) = (j-i+1)! / (3! * (j-i+1-3)!)

于 2012-08-28T12:28:57.663 に答える