摘要： 在合理的“概率分布”假设下,分析了两个有序表合并排序算法的平均情形复杂性,并将此结果应用于个元素的二分排序算法中,最后对二分排序算法的平均情形复杂性进行了估计。
关键词:
有序表,
合并排序,
平均情形复杂性,
二分排序
Abstract: On the hypothesis of a reasonable "probability distribution", this paper analyzes the average complexity of the ordering-by-merging algorithm of two ordered lists and applies the result to the complexity of binary ordering algorithm. In conclusion, an estimate on the average complexity of binary ordering algorithm is achieved.
中图分类号:
曹清录,王念平,张斌. 合并排序算法的平均情形复杂性分析及其应用[J]. , 2004, 30(21): 78-.
CAO Qinglu, WANG Nianping, ZHANG Bin. On Average Complexity of the Ordering-by-merging Algorithm and Its Application[J]. , 2004, 30(21): 78-.