| 用于IC版图运算的O(N)排序算法 |
| |
| 引用本文： | 李刚,林争辉.用于IC版图运算的O(N)排序算法[J].上海交通大学学报,1999,33(5):538-541. |
| |
| 作者姓名： | 李刚 林争辉 |
| |
| 作者单位： | 上海交通大学,大规模集成电路研究所,上海,200030 |
| |
| 基金项目： | 国家“九五”科技攻关预研资助 |
| |
| 摘 要： | 扫描线算法是集成电路版图运算的主流算法，排序在其中占有相当大的工作量．针对集成电路版图的特点，提出一种线性的排序算法，其时间复杂度为Ｏ（Ｎ），比通常的快速排序算法时间复杂度（Ｏ（ＮｌｏｇＮ）低，适用于基于扫描线算法的集成电路版图运算．对于层次式设计的版图，该算法更具优越性
|
| 关 键 词： | 集成电路 版图验证 层次式 扫描线 |
| 修稿时间： | 1998-07-07 |
O(N) Sorting Algorithm for IC Layout Graph Operation |
| |
| LI Gang,LIN Zheng-hui.O(N) Sorting Algorithm for IC Layout Graph Operation[J].Journal of Shanghai Jiaotong University,1999,33(5):538-541. |
| |
| Authors: | LI Gang LIN Zheng-hui |
| |
| Abstract: | The scan line algorithm is the main algorithm for IC layout graph operation, in which the sorting costs considerable time. Usually, a quick sorting algorithm is used whose time complexity is O(N log N) in average and O(N 2) in the worst case ( N is the sum of sorted elements).According to the character of IC layout, a linear sorting algorithm whose time complexity is O(N) was presented. It is adapted to the IC layout graph operation based on scan line algorithm. For hierarchical designed IC layout, it has much advantage. |
| |
| Keywords: | integrated circuit layout verification hierarchical scan line |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
