矩阵连乘动态规划时间复杂度

[season95]

矩阵连乘动态规划时间复杂度书上写的O(n三方)，原因是有三层for循环。但是子问题个数只有n平方量级个，而且三个for循环并不都是完整的for循环。所以如果循环体内复杂度为O(1)，那为什么复杂度不是O(n方)?

[ShenghaiRong]

子问题个数O(n^2),每个子问题的复杂度为O(n),所以复杂度是O(n^3). 动态规划问题的复杂度基本可以用子问题个数乘以每个子问题复杂度得到。

[season95]

子问题个数O(n^2),每个子问题的复杂度为O(n),所以复杂度是O(n^3). 动态规划问题的复杂度基本可以用子问题个数乘以每个子问题复杂度得到。

子问题复杂度为什么是O(n)呢？

[ShenghaiRong]

根据递推公式得到。

[season95]

根据递推公式得到。

明白了，谢谢助教。 我的上一个issue也想请教一下！

[season95]

最优三角剖分问题 和 矩阵加括号问题 很相似，且递归式一样，为什么三角剖分复杂度是O(n^2)而矩阵是O(n^3)?

[ShenghaiRong]

三角剖分复杂度也是O(n^3)，仔细看ppt，O(n^2)是子问题个数。然后开了issue的问题不用关了，如果其他人有类似疑问也能看得到。

[season95]

三角剖分复杂度也是O(n^3)，仔细看ppt，O(n^2)是子问题个数。然后开了issue的问题不用关了，如果其他人有类似疑问也能看得到。

好的，谢谢助教。