28-算法解析及优化拓展

6.4.6　算法解析及优化拓展

1．算法复杂度分析

（1）时间复杂度

分支限界法求布线问题，按照m叉树（m=4）的分析，空间树最坏情况下的结点为4ⁿ个，而空间树的深度n却是未知的，因此通过这种方法很难确定该算法的时间复杂度。那怎么办呢？我们要看看到底生成了多少个结点。

实际上，每个方格进入活结点队列最多1次，不会重复进入，因此对于m×n的方格阵列，活结点队列最多处理O(mn)个活结点，生成每个活结点需要O(1)的时间，因此算法时间复杂度为O(mn)。构造最短布线路径需要O(L)时间，其中L为最短布线路径长度。

（2）空间复杂度

空间复杂度为O(n)。

2．算法优化拓展

大家可以动手写写，如果不用分支限界法，而是按照求特殊的最短路径问题，算法的复杂度如何呢？是不是比单源最短路径Dijkstra算法简单多了？