此關係的時間複雜度 - 矩陣鏈乘法

我覺得對於矩陣鏈乘法問題的（低效率）遞歸過程可以在此（基於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)]

在這裏，要被相乘的矩陣=數。

T（n）的值是多少？

來源

2012-08-28 Jatin

它應該是q = INF或q = max（） –

已更正。 q = INF – Jatin

你在問http://en.wikipedia.org/wiki/Catalan_number嗎？ :) – Ankush

這是http://en.wikipedia.org/wiki/Catalan_number

您可以查看遞推關係因爲這樣做插入語。維基頁面詳細描述瞭如何到達公式。

來源

2012-08-28 12:20:05 Ankush

我不知道如何解決我提到的遞歸關係（即T（n）= k從k變化到j [T（k）+ T（nk）]）的總和。那麼，我怎麼知道它轉化爲加泰羅尼亞數字？ – Jatin

@jatin你最好在數學論壇上提出解決復發問題。這裏的解決方案是加泰羅尼亞號。它是$ \ omega {2^n} $ – Geek

這可能有所幫助：

您只需制定每個矩陣鏈（並存儲其值）即可。

開始= i和j之間的任何

末=開始和j

K =開始之間，並最終

如果我們認爲一些具有全0除了三個1之間的任何地方的任何地方（代表開始，k，結束）

這個特殊號碼有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 =組合（3，J-I + 1）

此是n!/(k! * (n-k)!) = (j-i+1)!/(3! * (j-i+1-3)!)

來源

2012-08-28 12:28:57

此關係的時間複雜度 - 矩陣鏈乘法

回答

相關問題