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

11

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) kk

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. kO(n)kO(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 ) ?n/2O(n)O(n)

user834
la source

Réponses:

13

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(n1+ε)O(1/ε)ε>0

O(n)pp

pA(k)ε=1/kA(k)A(k1)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.

A.Schulz
la source