Fast computation of the median by successive binning
作者： Ryan J. Tibshirani
DOI:
关键词:
摘要: This paper describes a new median algorithm and approximation algorithm. The former has O(n) average running time the latter worst-case time. These algorithms are highly competitive with standard when computing of single data set, but significantly faster in updating more is added.
arxiv.org
harvard.edu参考文章(4)
Robert W. Floyd, Ronald L. Rivest, Expected time bounds for selection Communications of The ACM. ,vol. 18, pp. 165- 172 ,(1975) , 10.1145/360680.360691
Leonidas Guibas, Feng Zhao, Wireless Sensor Networks: An Information Processing Approach Morgan Kaufmann Publishers Inc.. ,(2004)
C. A. R. Hoare, Algorithm 64: Quicksort Communications of the ACM. ,vol. 4, pp. 321- ,(1961) , 10.1145/366622.366644
Rajeev Motwani, Prabhakar Raghavan, Randomized Algorithms ,(1995)