http://scholars.ntou.edu.tw/handle/123456789/14576
標題: | Transitional behaviors of the average cost of quicksort with median-of-(2t + 1) | 作者: | Hua-Huai Chern H. -K. Hwang |
關鍵字: | Quicksort;Phase transition;Ordinary differential equation;Uniform asymptotics;Binary search tree;Insertion sort;Recurrence relations | 公開日期: | 2001 | 出版社: | Springer Nature | 卷: | 29 | 起(迄)頁: | 44-69 | 來源出版物: | Algorithmica | 摘要: | A fine analysis is given of the transitional behavior of the average cost of quicksort with median-of-three. Asymptotic formulae are derived for the stepwise improvement of the average cost of quicksort when iterating median-of-threek rounds for all possible values ofk. The methods used are general enough to apply to quicksort with median-of-(2t + 1) and to explain in a precise manner the transitional behaviors of the average cost from insertion sort to quicksort proper. Our results also imply nontrivial bounds on the expected height, “saturation level,” and width in a random locally balanced binary search tree. |
URI: | http://scholars.ntou.edu.tw/handle/123456789/14576 | DOI: | 10.1007/BF02679613 |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。