Lié à l'espace pour l'algorithme de sélection?

Il existe un algorithme de sélection le pire des cas bien connu pour trouver le k ième élément le plus grand dans un tableau d'entiers. Il utilise une médiane des-médianes approche pour trouver un pivot assez bon, les partitions du tableau d'entrée de en place, puis continue récursive en elle recherche de la k « e plus grand élément.$O(n)$ $k$$k$

Que faire si nous n'étions pas autorisés à toucher le tableau d'entrée, combien d'espace supplémentaire serait nécessaire pour trouver le ième élément le plus grand en temps O ( n ) ? Pouvons-nous trouver le k ième élément le plus grand dans l' espace supplémentaire O ( 1 ) tout en conservant le temps d'exécution O ( n ) ? Par exemple, la recherche de l'élément maximum ou minimum prend O ( n ) temps et O ( 1 ) espace. $k$$O(n)$$k$$O(1)$$O(n)$$O(n)$$O(1)$

Intuitivement, je ne peux pas imaginer que nous pourrions faire mieux que l' espace mais y a-t-il une preuve de cela?$O(n)$

Quelqu'un peut-il pointer vers une référence ou trouver un argument pour expliquer pourquoi le ième élément exigerait que l' espace O ( n ) soit trouvé en temps O ( n ) ?$\lfloor n/2 \rfloor$$O(n)$$O(n)$

C'est un problème ouvert si vous pouvez faire une sélection avec temps et O ( 1 ) cellules mémoire supplémentaires sans changer l'entrée (voir ici ). Mais vous pouvez vous en approcher.$O(n)$$O(1)$

$O(n^{1+\varepsilon})$$O(1/\varepsilon)$$\varepsilon>0$

$O(n)$$p$$p$

$p$$A(k)$$\varepsilon=1/k$$A(k)$$A(k-1)$$A(1)$algorithme. La bonne taille de bloc (et le calcul) vous donne le temps d'exécution et l'espace requis comme indiqué ci-dessus.

Btw, les algorithmes que vous recherchez, ont récemment été nommés algorithmes à espace de travail constant .

Je n'ai connaissance d'aucune borne inférieure.