On fine fluctuations of the complexity of the QuickSelect algorithm
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916544041189376 |
|---|---|
| author | Ischebeck, Jasper Neininger, Ralph |
| author_facet | Ischebeck, Jasper Neininger, Ralph |
| contents | The Quickselect algorithm (also called FIND) is a fundamental algorithm for selecting ranks or quantiles within a set of data. Grübel and Rösler showed that the number of key comparisons required by Quickselect considered as a process of the quantiles $α\in[0,1]$ converges within a natural probabilistic model after normalization in distribution within the càdlàg space $D[0,1]$ endowed with the Skorokhod metric. We show that the residual process in the latter convergence after normalization converges in distribution towards a mixture of Gaussian processes in $D[0,1]$. A similar result holds for the related algorithm QuickVal. Our method is applicable to other cost measures such as the number of swaps (key exchanges) required by Quickselect, or cost measures being based on key comparisons taking additionally into account that the cost of a comparison between two keys may depend on their values, an example being the number of bit comparisons needed to compare keys given by their bit expansions. For all the arising mixtures of Gaussian limit processes, we also discuss the Hölder continuity of their paths. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_07685 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On fine fluctuations of the complexity of the QuickSelect algorithm Ischebeck, Jasper Neininger, Ralph Probability 60F17, 68Q25, 68P10, 60C05 The Quickselect algorithm (also called FIND) is a fundamental algorithm for selecting ranks or quantiles within a set of data. Grübel and Rösler showed that the number of key comparisons required by Quickselect considered as a process of the quantiles $α\in[0,1]$ converges within a natural probabilistic model after normalization in distribution within the càdlàg space $D[0,1]$ endowed with the Skorokhod metric. We show that the residual process in the latter convergence after normalization converges in distribution towards a mixture of Gaussian processes in $D[0,1]$. A similar result holds for the related algorithm QuickVal. Our method is applicable to other cost measures such as the number of swaps (key exchanges) required by Quickselect, or cost measures being based on key comparisons taking additionally into account that the cost of a comparison between two keys may depend on their values, an example being the number of bit comparisons needed to compare keys given by their bit expansions. For all the arising mixtures of Gaussian limit processes, we also discuss the Hölder continuity of their paths. |
| title | On fine fluctuations of the complexity of the QuickSelect algorithm |
| topic | Probability 60F17, 68Q25, 68P10, 60C05 |
| url | https://arxiv.org/abs/2403.07685 |