此关系的时间复杂度 - 矩阵链乘法

我觉得对于矩阵链乘法问题的（低效率）递归过程可以在此（基于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

此关系的时间复杂度 - 矩阵链乘法

回答

相关问题