algorithm - 您如何计算矩阵链乘法的简单解决方案的运行时间？

Question

我正在研究矩阵链乘法。并且朴素的解决方案相当于问题的加泰罗尼亚数。

这就是它在解决方案中所说的。通过将括号问题减少到二叉树，天真的解决方案最终成为 O(2^n)。然后计算给定输入的所有二叉树。

我只是不明白你是如何从括号矩阵链乘法到二叉树的。我自己永远也想不通。

Answer 1

回答我自己的问题。二叉表达式树并不是一个新概念。我们正在处理二元运算，因此我们可以将括号转换为二元表达式树。然后问自己，有多少个二叉表达式树？

对 K-ary 表达式树的问题进行运行时分析可能​​很有趣。