随着集成电路技术的发展，器件的特征尺寸不断减小。越来越小的器件尺寸给集成电路设计带来了许多新的问题，时序收敛是最突出的问题之一。在集成电路时序中，互连线时序占据了越来越重要的地位。当工艺尺寸进入到纳米尺寸之后，互连线延时超过了门延时，成为了影响芯片总延时的关键因素。因此，为了满足高性能芯片的时序收敛要求，互连线的时序优化变得非常重要。缓冲器插入是互连线时序优化的主要策略之一。对于特定的布局树，在适当的节点插入缓冲器可以起到降低互连线关键路径延时的作用。为了找到最优的缓冲器插入方式，需要研究快速的缓冲器插入优化算法。针对不同的缓冲器种类、布局树中漏端的数目和缓冲器待插节点数目，以往研究已经提出了不同时间复杂度的缓冲器插入时序优化算法，如时间复杂度为O(b2nlog2n)的算法。当待插节点数目较大时，该算法的效率仍旧比较低。为了提高算法在缓冲节点数目较大时的效率，论文提出了时间复杂度为O(b2n+bmn)的算法。当漏端数目固定时，该算法明显优于时间复杂度为O(b2nlog2n)的算法。这是通过两个关键性技术来实现的：新的冗余solution删除规则以及交叉节点预测技术。新的冗余solution删除规则能够最大限度的删除冗余solution，经过冗余删除之后的solution具有特殊的性质，该性质是实现算法线性时间复杂度的关键因素。交叉节点预测技术是通过采用特殊的数据结构，使得算法能够预判下一节点是否为交叉节点，并提前采取不同的冗余solution删除规则。实验结果表明，对于同一电路，新算法的运行速度与以往最优算法的运行速度相比提高了50%左右。