Si je marche dans la liste et supprimez chaque élément hors commandement, je rencontre en moyenne combien d'éléments resteront?

Question

J'ai une liste de longueur de longueur uniformément permutée de manière aléatoire $ n $ . Je traverse la liste Élément-par-élément et supprimez un élément s'il est hors de commande (par rapport aux éléments précédents de la liste de la liste). Ce qui me reste est une liste plus courte qui est garantie pour être en ordre.

Exemple: les éléments étoilés de cette liste seraient supprimés pendant la marche.

[1, 4, 2 *, 3 *, 5, 7, 6 *] -> [1, 4, 5, 7]

Ma question est la suivante: En moyenne, quelle sera la durée de la liste restante? Et y a-t-il une forme simple / évidente de la distribution de cela?

Et comme un suivi: si nous l'utilisions pour un algorithme de tri (appelé Tri de Drop), quel serait le temps d'exécution? Pour être clair, l'algorithme serait quelque chose comme ceci: $$ \ textit {dropsort} (\ text {liste})=texticules {fusion} (\ Text {liste restante}, \ textit {dropsort} (\ Text {list {DROPSORT} )) $$

Cette question a été inspirée de ce R / programmerhumor Post .

Answer 1

Vous pouvez calculer la moyenne en utilisant la linéarité d'attente.

Laissez la variable aléatoire $ x $ dénote le nombre d'éléments retenus. Laissez $ x_i $ être un indicateur R.V. C'est 1 si la $ I $ TH ELEMENT est conservé, ou 0 sinon. Alors $ x= x_1 + \ dots + x_n $ , donc

$$ \ mathbb {e} [x]=mathbb {e} [x_1] + \ dots + \ mathbb {e} [x_n]=pr [x_1= 1] + \ points + \ pr [x_n= 1]. $$

maintenant la $ i $ TH élément est conservé si et seulement s'il s'agit du plus grand nombre parmi la première $ i $ éléments de la liste. Par conséquent, $ \ pr [x_i= 1]=frac {1} {i} $ , donc

$$ \ mathbb {e} [x]=frac {1} {1} + \ frac {1} {2} + \ points + \ frac {1} {n} \ envies \ log (n) + \ gamma $$

En d'autres termes, la longueur moyenne de la liste restante est $ o (\ journal n) $ .

.

Je ne sais pas quelle est la distribution.

comme une heuristique, l'heure de fonctionnement attendue de la sorte de chute satisferait une récurrence quelque chose comme $ t (n) \ environ t (n \ log (n)) + o ( n) $ , qui correspond à $ o \ gauche (\ frac {n ^ 2} {\ journal n} \ droite) $ temps.