27-算法解析及优化拓展

4.5.6　算法解析及优化拓展

1．算法复杂度分析

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

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

2．算法优化拓展

如果只是想得到最优值（最少的租金），则不需要s[][]数组；m[][]数组也可以省略，直接在r[][]数组上更新即可，这样空间复杂度减少为O(1)。