| 利用树状数组的两区域电路线交叉分布 |
| |
| 引用本文： | 邓新国,高董英,郭朝珍,肖如良.利用树状数组的两区域电路线交叉分布[J].福州大学学报(自然科学版),2013,41(6):1028-1034. |
| |
| 作者姓名： | 邓新国 高董英 郭朝珍 肖如良 |
| |
| 作者单位： | 福州大学数学与计算机科学学院，福建 福州 350116;福州大学数学与计算机科学学院，福建 福州 350116;福州大学数学与计算机科学学院，福建 福州 350116;福建师范大学软件学院，福建 福州 350117 |
| |
| 摘 要： | 在两区域电路线交叉分布中计算交叉点的数目，目前采用线性表或者动态规划的方法，其算法时间复杂性均为O(n2). 为有效降低现有算法的时间复杂性，给出一种时间复杂性为O（nlogn）、利用树状数组的计数算法，并且可以找到每条布线的所有交叉线. 理论分析和相应实验结果证实了该算法的有效性.
|
| 关 键 词： | 电路布线 交叉分布 交叉线 树状数组 |
Crossing distribution of circuit wires between two regions using arborescence array |
| |
| DENG Xin-guo,GAO Dong-ying,GUO Chao-zhen and XIAO Ru-liang.Crossing distribution of circuit wires between two regions using arborescence array[J].Journal of Fuzhou University(Natural Science Edition),2013,41(6):1028-1034. |
| |
| Authors: | DENG Xin-guo GAO Dong-ying GUO Chao-zhen and XIAO Ru-liang |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《福州大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《福州大学学报(自然科学版)》下载免费的PDF全文 |
