https://scholars.lib.ntu.edu.tw/handle/123456789/624642
標題: | Sorting with recurrent comparison errors | 作者: | Geissmann B Leucci S Liu C.-H Penna P. CHIH-HUNG LIU |
關鍵字: | Maximum and total dislocation; Recurrent comparison error; Sorting | 公開日期: | 2017 | 卷: | 92 | 來源出版物: | Leibniz International Proceedings in Informatics, LIPIcs | 摘要: | We present a sorting algorithm for the case of recurrent random comparison errors. The algorithm essentially achieves simultaneously good properties of previous algorithms for sorting n distinct elements in this model. In particular, it runs in O(n2) time, the maximum dislocation of the elements in the output is O(log n), while the total dislocation is O(n). These guarantees are the best possible since we prove that even randomized algorithms cannot achieve o(log n) maximum dislocation with high probability, or o(n) total dislocation in expectation, regardless of their running time. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85038582404&doi=10.4230%2fLIPIcs.ISAAC.2017.38&partnerID=40&md5=49ce5a919d2fc43f23cf93180d0b9303 https://scholars.lib.ntu.edu.tw/handle/123456789/624642 |
ISSN: | 18688969 | DOI: | 10.4230/LIPIcs.ISAAC.2017.38 | SDG/關鍵字: | Errors; Sorting; Distinct elements; High probability; Randomized Algorithms; Running time; Sorting algorithm; Random errors |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。