34-算法解析及优化拓展

4.6.6　算法解析及优化拓展

1．算法复杂度分析

（1）时间复杂度：由程序可以得出：语句 t= m[i][k] + m[k+1][j] +p[i−1]p[k]p[j]，它是算法的基本语句，在3层for循环中嵌套。最坏情况下，该语句的执行次数为O(n³)，print()函数算法的时间主要取决于递归，时间复杂度为O(n)。故该程序的时间复杂度为O(n³)。

（2）空间复杂度：该程序的输入数据的数组为p[]，辅助变量为i、j、r、t、k、m[][]、s[][]，空间复杂度取决于辅助空间，因此空间复杂度为O(n²)。

2．算法优化拓展

想一想，还有什么办法对算法进行改进，或者有什么更好的算法实现？