13-算法解析及优化拓展

4.3.6　算法解析及优化拓展

1．算法复杂度分析

（1）时间复杂度：由于每个数组单元的计算耗费Ο(1)时间，如果两个字符串的长度分别是m、n，那么算法时间复杂度为Ο(m*n)。

（2）空间复杂度：空间复杂度主要为两个二维数组c[][]，b[][]，占用的空间为O(m*n)。

2．算法优化拓展

因为c[i][j]有3种来源：c[i−1][j−1]+1、c[i][j−1]、c[i−1][j]。我们可以利用c数组本身来判断来源于哪个值，从而不用b[][]，这样可以节省O(mn)个空间。但因为c数组还是O(mn)个空间，所有空间复杂度数量级仍然是O(m*n)，只是从常数因子上的改进。仍然是倒推的办法，如图4-17所示，读者可以想一想怎么做？