行列の鎖の乗算の時間の複雑さ

Question

これは、Cormenらによる "Introduction to Algorithms"で解決された問題です。 al。 Ch。 15、セクション15.2：行列連鎖の乗算。 Pg。目的は、最小数のスカラー倍算が存在するように、行列連鎖積A1.A2.A3 .....をかっこで囲むことです。
についてAi.Ai + 1 .... Ak.Ak + 1 ..... Ajと、
行列Aiは、ディメンションPI-1xpi を持っている著者は、再帰

m[i,j] = 0 if i=j 
     = min {m[i,k] + m[k+1] + pi-1.pk.pj} where i goes from k to (j-1) if i<j 

を思い付きます

（m [i、j]は、Ai ... Ajの積に必要なスカラー乗算の最小数）

これまでのところ、私は理解しましたが、時間の複雑さはO（n^3） 。
私は擬似コードを見ると、3つのforループがあるので正しいです。しかし、私は再帰を見ることでこれを直感的に理解しません。

誰でもお手伝いできますか？

Answer 1

最後の解決策は、m[0,N]を計算することです。しかし、m[i,j]のすべての値を計算してから、m[0,N]を計算する必要があります。これはO(N^2)になります。

再帰式からは、それぞれm[i,j]の計算が複雑であることがわかります。O(N)複雑です。

so O(N^3)完全な解決策です。

Answer 2

任意のMCM問題に対してO（n^2）個の固有の問題が存在する可能性があり、そのようなすべての問題に対してO（n）個の分割が可能である可能性があります。

だからO（n^3）です。