How robust are average complexity measures? A statistical case study
作者：
Highlights：
•
摘要
In the present paper, the authors reject one of Knuth’s well known results on average case complexity in replacement (i.e. selection) sort and hence challenge the robustness of average complexity measures where the response variable is sensitive to ties.
论文关键词：Algorithm,Robustness,Average case complexity,Worst-case complexity,Replacement sort
论文评审过程：Available online 10 January 2007.
论文官网地址：https://doi.org/10.1016/j.amc.2006.12.068
