计算机工程与设计
計算機工程與設計
계산궤공정여설계
COMPUTER ENGINEERING AND DESIGN
2012年
11期
4062-4065
,共4页
特殊有向单位步长%双环网络%寻径%算法%时间空间特性
特殊有嚮單位步長%雙環網絡%尋徑%算法%時間空間特性
특수유향단위보장%쌍배망락%심경%산법%시간공간특성
直径的求解是双环网络的最关键问题,为更好求解双环网络直径,文中选择一个步长为1的有向单位步长双环网络,针对另一个步长h的取值为最小值2,中间值N/2、(N/2)+1(N为偶数)或者中间值(N+1)/2(N为奇数)和最大值N-1这3种情况所构成的几类双环网络,给出了寻径算法,对这几种算法的特点进行了分析和比较,并对这几种算法的时间和空间特性进行了比较分析,得出它们的时间复杂度和空间复杂度都是Ω(N/2).
直徑的求解是雙環網絡的最關鍵問題,為更好求解雙環網絡直徑,文中選擇一箇步長為1的有嚮單位步長雙環網絡,針對另一箇步長h的取值為最小值2,中間值N/2、(N/2)+1(N為偶數)或者中間值(N+1)/2(N為奇數)和最大值N-1這3種情況所構成的幾類雙環網絡,給齣瞭尋徑算法,對這幾種算法的特點進行瞭分析和比較,併對這幾種算法的時間和空間特性進行瞭比較分析,得齣它們的時間複雜度和空間複雜度都是Ω(N/2).
직경적구해시쌍배망락적최관건문제,위경호구해쌍배망락직경,문중선택일개보장위1적유향단위보장쌍배망락,침대령일개보장h적취치위최소치2,중간치N/2、(N/2)+1(N위우수)혹자중간치(N+1)/2(N위기수)화최대치N-1저3충정황소구성적궤류쌍배망락,급출료심경산법,대저궤충산법적특점진행료분석화비교,병대저궤충산법적시간화공간특성진행료비교분석,득출타문적시간복잡도화공간복잡도도시Ω(N/2).
