Si camino a través de la lista y elimino cada elemento de salida, me encuentro, en promedio, ¿cuántos elementos se dejarán?

Question

Tengo una lista de longitud de longitud de longitud uniformemente permitida $ n $ . Camino a través de la lista de elementos por elemento por elemento, y eliminé un elemento si está fuera de orden (en comparación con los elementos anteriores de la lista). Lo que me queda es una lista más corta que está garantizada para estar en orden.

Ejemplo: Los elementos protagonizados de esta lista se eliminarían durante el paseo.

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

Mi pregunta es: en promedio, ¿cuál será la longitud de la lista restante? ¿Y hay alguna forma simple / obvia de la distribución de esto?

y como un seguimiento: si usamos esto para un algoritmo de clasificación (llamado Sort Ordenar), ¿cuál será el tiempo de ejecución? Para ser claro, el algoritmo sería algo así: $$ \ textit {dropsort} (\ texto {list})=textit {funge} (\ texto {lista restante}, \ textit {dropsort} (\ texto {lista rechazada} )) $$

Esta pregunta se inspiró en este r / programmerhumor post .

Answer 1

Puede calcular el promedio utilizando la linealidad de la expectativa.

Deja que la variable aleatoria $ x $ denota el número de elementos que se conservan. Deje que $ x_i $ sea un indicador R.V. Eso es 1 si el $ i $ se mantiene el elemento, o 0 de lo contrario. Luego $ x= x_1 + \ dots + x_n $ , por lo que

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

Ahora el $ i $ El elemento se conserva si es y solo si es el número más grande entre el primer $ i $ elementos en la lista. Por lo tanto, $ \ pr [x_i= 1]=frac {1} {i} $ , por lo

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

En otras palabras, la longitud promedio de la lista restante es $ o (\ log n) $ .

No sé cuál es la distribución.

Como heurística, el tiempo de ejecución esperado de la gota de gota satisfará una recurrencia algo como $ t (n) \ aprox t (n- \ log (n)) + o ( n) $ , que corresponde a $ o \ izquierda (\ frac {n ^ 2} {\ log n} \ derecha) $ tiempo.