计算机应用
計算機應用
계산궤응용
COMPUTER APPLICATION
2008年
1期
245-247
,共3页
线对象%邻接关系%桶排序%算法分析
線對象%鄰接關繫%桶排序%算法分析
선대상%린접관계%통배서%산법분석
给定向量化坐标,计算n个线对象两两邻接关系,普通算法时间复杂度为O(n*n);理论最好时间复杂度为O(C),其中C是邻接关系的基数.基于散列桶,给出了建立线对象邻接关系的快速算法,其平均时间复杂度为O(n(1+1/r)),r为算法分配的桶数量与n的比,空间复杂度为O(n).证明了若不允许使用额外空间,则不可能使用排序算法解决该问题;给出了允许使用额外空间条件下的两遍排序算法,时间复杂度为O(n(lb n+1+2/r)).应用表明快速算法比普通算法速度提高1～3个数量级.
給定嚮量化坐標,計算n箇線對象兩兩鄰接關繫,普通算法時間複雜度為O(n*n);理論最好時間複雜度為O(C),其中C是鄰接關繫的基數.基于散列桶,給齣瞭建立線對象鄰接關繫的快速算法,其平均時間複雜度為O(n(1+1/r)),r為算法分配的桶數量與n的比,空間複雜度為O(n).證明瞭若不允許使用額外空間,則不可能使用排序算法解決該問題;給齣瞭允許使用額外空間條件下的兩遍排序算法,時間複雜度為O(n(lb n+1+2/r)).應用錶明快速算法比普通算法速度提高1～3箇數量級.
급정향양화좌표,계산n개선대상량량린접관계,보통산법시간복잡도위O(n*n);이론최호시간복잡도위O(C),기중C시린접관계적기수.기우산렬통,급출료건립선대상린접관계적쾌속산법,기평균시간복잡도위O(n(1+1/r)),r위산법분배적통수량여n적비,공간복잡도위O(n).증명료약불윤허사용액외공간,칙불가능사용배서산법해결해문제;급출료윤허사용액외공간조건하적량편배서산법,시간복잡도위O(n(lb n+1+2/r)).응용표명쾌속산법비보통산법속도제고1～3개수량급.
