计算机技术与发展
計算機技術與髮展
계산궤기술여발전
COMPUTER TECHNOLOGY AND DEVELOPMENT
2010年
8期
33-36
,共4页
算法%表插入排序%查找%时间复杂度
算法%錶插入排序%查找%時間複雜度
산법%표삽입배서%사조%시간복잡도
表插入排序算法的优点在于其避免了记录的移动,算法执行的花销主要在于查找插入位置,平均时间复杂度为O(n2/4).针对表插入排序算法中每次查找插入位置均需从表头开始的限制,提出了新的表插入排序算法,给出了相关算法描述及性能分析.大量实验表明,新的表插入排序算法的平均时间复杂度为O(n2/6),而查找插入位置所需进行的元素比较的次数平均减少了33%.结果显示虽然平均时间复杂度与其他的表插入排序算法相当,但元素比较的次数却有了很大的降低,为下一步与折半查找相结合提供了方向.
錶插入排序算法的優點在于其避免瞭記錄的移動,算法執行的花銷主要在于查找插入位置,平均時間複雜度為O(n2/4).針對錶插入排序算法中每次查找插入位置均需從錶頭開始的限製,提齣瞭新的錶插入排序算法,給齣瞭相關算法描述及性能分析.大量實驗錶明,新的錶插入排序算法的平均時間複雜度為O(n2/6),而查找插入位置所需進行的元素比較的次數平均減少瞭33%.結果顯示雖然平均時間複雜度與其他的錶插入排序算法相噹,但元素比較的次數卻有瞭很大的降低,為下一步與摺半查找相結閤提供瞭方嚮.
표삽입배서산법적우점재우기피면료기록적이동,산법집행적화소주요재우사조삽입위치,평균시간복잡도위O(n2/4).침대표삽입배서산법중매차사조삽입위치균수종표두개시적한제,제출료신적표삽입배서산법,급출료상관산법묘술급성능분석.대량실험표명,신적표삽입배서산법적평균시간복잡도위O(n2/6),이사조삽입위치소수진행적원소비교적차수평균감소료33%.결과현시수연평균시간복잡도여기타적표삽입배서산법상당,단원소비교적차수각유료흔대적강저,위하일보여절반사조상결합제공료방향.
