Selection algorithm: Difference between revisions

Revision as of 19:32, 1 April 2023

Revision as of 19:33, 1 April 2023

Line 34:

===Parallel algorithms===

[[Parallel algorithm]]s for selection have been studied since 1975, when [[Leslie Valiant]] introduced the parallel comparison tree model for analyzing these algorithms, and proved that in this model selection using a linear number of comparisons requires <math>\Omega(\log\log n)</math> parallel steps, even for selecting the minimum or {{nowrap|maximum.{{r|valiant}}}} Researchers later found parallel algorithms for selection in <math>O(\log\log n)</math> steps, matching this {{nowrap|bound.{{r|akss|azapip}}}} In a randomized parallel comparison tree model it is possible to perform selection in a bounded number of steps and a linear number of {{nowrap|comparisons.{{r|reischuk}}}} On the more realistic [[parallel RAM]] model of computing, with exclusive read exclusive write memory access, selection can be performed in time <math>O(\log n)</math> with <math>O(n/\log n)</math> processors, which is optimal both in time and in the number of {{nowrap|processors.{{r|han}}}} With concurrent memory access, slightly faster parallel time is possible in {{nowrap|general,{{r|chr}}}} and the <math>\log n</math> term in the time bound can be replaced {{nowrap|by <math>\log k</math>,.{{r|dieram}}}}

===Sublinear data structures===