利用树状数组的两区域电路线交叉分布

Crossing distribution of circuit wires between two regions using arborescence array

在两区域电路线交叉分布中计算交叉点的数目,目前采用线性表或者动态规划的方法,其算法时间复杂性均为O(n2).为有效降低现有算法的时间复杂性,给出一种时间复杂性为O(nlogn)、利用树状数组的计数算法,并且可以找到每条布线的所有交叉线.理论分析和相应实验结果证实了该算法的有效性.

Counting the crossing wires in the crossing distribution of circuit wires between two regions, the current algorithms using either linear list or dynamic programming to do so have the time complexi- ty O （n2 ）. In order to reduce the time complexity of the existing algorithms efficiently, a counting al- gorithm with the time complexity of O （nlogn） using arborescence array is introduced in this paper. Furthermore, all crossing wires of every circuit wire are found with this algorithm. The effectiveness of the algorithm is illustrated through the theoretical analysis and by the corresponding experiment re- sults.