Dans un article classique, Munro et Paterson étudient le problème de la quantité de stockage requise pour qu'un algorithme trouve la médiane dans un tableau trié de manière aléatoire. En particulier, ils se concentrent sur le modèle suivant:
l'entrée est lue de gauche à droite pendant un nombre P de fois.
On montre que cellules mémoire sont suffisantes, mais la borne inférieure correspondante n'est connue que pour P = 1. Je n'ai vu aucun résultat pour P> 1. Quelqu'un est-il au courant de ces limites inférieures?
Notez que la principale difficulté ici est qu'à la deuxième passe, l'entrée n'est plus ordonnée de manière aléatoire.
ds.algorithms
space-bounded
data-streams
MassimoLauria
la source
la source
Le premier papier à prouver les limites de plus d'un passage a été mon papier avec Jayram et Amit de SODA'08. Ensuite, il y a le papier mentionné par Warren, qui améliore les limites par une preuve plus propre.
En bref, nous comprenons la dépendance si vous autorisez des constantes devant le nombre de passes. Bien sûr, ces constantes sont dans l'exposant, vous pouvez donc demander une compréhension précise. Ma principale plainte est que le modèle de streaming multipass n'est pas très bien motivé.
La question la plus intrigante est de savoir si nous pouvons prouver une limite inférieure d'un programme de branchement. Se peut-il que même pour un algorithme d'espace délimité qui puisse accéder à la mémoire à sa guise, la meilleure stratégie consiste à ne faire que du streaming multipass?
La réponse semble être affirmative, et nous avons des progrès partiels pour le prouver.
la source