Optimal parallel selection had complexity O (log log N )
作者： Miklós Ajtai , János Komlós , W.L. Steiger , Endre Szemerédi
DOI: 10.1016/0022-0000(89)90035-4
关键词: Selection (genetic algorithm) 、 Sorting 、 Upper and lower bounds 、 Log-log plot 、 Combinatorics 、 Time optimal 、 Set (abstract data type) 、 Mathematics 、 Order (group theory)
摘要: Abstract We show that in the deterministic comparison model for parallel computation, p = n processors can select kth smallest item from a set of numbers O(log log n) time. With this result all tasks (selection, merging, sorting) now have upper and lower bounds same order both random models. This optimal time bound holds even if o ( ).
core.ac.uk
elsevier.com
sci-hub.se 参考文章(7)
A Lubotzky, R Phillips, P Sarnak, Explicit expanders and the Ramanujan conjectures symposium on the theory of computing. pp. 240- 246 ,(1986) , 10.1145/12130.12154
Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, Robert E. Tarjan, Time bounds for selection Journal of Computer and System Sciences. ,vol. 7, pp. 448- 461 ,(1973) , 10.1016/S0022-0000(73)80033-9
Ofer Gabber, Zvi Galil, Explicit constructions of linear-sized superconcentrators Journal of Computer and System Sciences. ,vol. 22, pp. 407- 420 ,(1981) , 10.1016/0022-0000(81)90040-4
Richard Cole, Chee K. Yap, A parallel median algorithm Information Processing Letters. ,vol. 20, pp. 137- 139 ,(1985) , 10.1016/0020-0190(85)90080-8
A. Borodin, J. E. Hopcroft, Routing, merging and sorting on parallel models of computation Proceedings of the fourteenth annual ACM symposium on Theory of computing - STOC '82. pp. 338- 344 ,(1982) , 10.1145/800070.802209
M. Ajtai, J. Komlós, E. Szemerédi, An 0(n log n) sorting network symposium on the theory of computing. pp. 1- 9 ,(1983) , 10.1145/800061.808726
Leslie G. Valiant, Parallelism in Comparison Problems SIAM Journal on Computing. ,vol. 4, pp. 348- 355 ,(1975) , 10.1137/0204030