摘要
给定向量化坐标，计算n个线对象两两邻接关系，普通算法时间复杂度为O（n＊n）；理论最好时间复杂度为O（C），其中C是邻接关系的基数。基于散列桶，给出了建立线对象邻接关系的快速算法，其平均时间复杂度为O（n（1＋1／r）），r为算法分配的桶数量与n的比，空间复杂度为O（n）。证明了若不允许使用额外空间，则不可能使用排序算法解决该问题；给出了允许使用额外空间条件下的两遍排序算法，时间复杂度为O（n（1bn＋1＋2／r））。应用表明快速算法比普通算法速度提高1—3个数量级。
Based on known coordinates of lines, the time complexity of usual algorithm for reconstructing adjacency relation among n line objects usually is O（n ＊ n） ; in theory, its optimal value is at least O（C） and C is the cardinal number of adjacency relation. Based on hashed-bucket sorting, a quick algorithm with O（ n（ 1 ＋ 1/r） ） average time complexity and with O（n） space complexity was given to reconstruct adjacency relation where r was the ratio of number of buckets used in the algorithm to n. It was proved that the problem can not be solved by sorting algorithm without extra space. With necessary extra space, a two-pass sorting algorithm with O[ n（ 1b n ＋ 1 ＋ 2/r） ] time complexity, was also given. Applications show that the performance of the quick algorithm is over about 1 - 3 orders of magnitude higher than that of the usual algorithm.
出处
《计算机应用》
CSCD
北大核心
2008年第1期245-247,共3页
journal of Computer Applications
关键词
线对象
邻接关系
桶排序
算法分析
line object
adjacency relation
hashed-bucket sorting
algorithm analysis
