12-算法解析及优化拓展

7.2.5　算法解析及优化拓展

1．算法复杂度分析

（1）时间复杂度：在输入基本变量和非基本变量中用了n+m的循环次数，在输入单纯形表时有nm次循环，在打印最优解时有n+nm次的时间打印结果，在寻找入基列和离基行中，最坏的情况下有O(n*m)次循环，在循环迭代中最坏情况下需要2ⁿ迭代，则时间复杂度为O(2ⁿ)。

（2）空间复杂度：计算空间复杂度时只计算辅助空间，在该程序中kernel[][]用来记录输入的单纯形表，用FJL[]来记录输入的非基本变量的值，用JL[]来记录输入的JL[]基本变量的值，辅助空间为一些变量和换基变换时的辅助变量，所以空间复杂度为O(1)。

2．算法优化拓展

想一想，还有没有更好的算法呢？