Dada una lista no clasificada de artículos de $ N $, ¿cuántas comparaciones aleatorias se necesitan en promedio para poder ordenar la lista?

Question

Hay una lista no clasificada de $ n $ artículos $ x_1, \ ldots, x_n $ . Hasta que pueda ordenar la lista, le dan uno de los $ {n \ elegir 2} $ posibles comparaciones binarias uniformemente al azar (con reemplazo).

En promedio, ¿cuántas de estas comparaciones aleatorias deberán poder ordenar la lista?

Algunas preguntas de seguimiento:

1. ¿Cómo se ve la distribución para el número de comparaciones?
2. ¿Cuál es la respuesta si usa $ k $ comparaciones arsenales en lugar de las binarias?
3. ¿Cuál es la respuesta si las comparaciones se realizan sin reemplazo (es decir, no obtendrás la misma comparación dos veces)?
4. Dado un conjunto de comparaciones, ¿cómo se puede revisar si la lista es ordenada? Estoy casi seguro de que la respuesta es construir una DAG y un tipo topológico, pero solo quiero confirmar.

Una respuesta exacta de ISH sería agradable, pero un gran contenedor de matemáticas "> $ o $ también está bien, supongo.

Answer 1

Asimpóticamente, necesitará $ \ theTa (n ^ 2 \ log n) $ comparaciones.

Supongamos $ x _ {(1)}, \ dots, x _ {(n)} $ denota los elementos en orden ordenado. Luego, si no ve una comparación entre $ x _ {(1)} $ y $ x _ {(2)} $ , no tendrá manera de saber en qué orden deberían aparecer. Lo mismo ocurre con cada par de elementos adyacentes. Por lo tanto, hay $ n-1 $ cupones (uno por par de elementos adyacentes), y necesita recogerlos a todos. Basado en la problema del colector de cupones , sabemos que necesitará $ \ THETA (n \ log n) $ Los cupones elegidos al azar antes de que los hayamos recogido a todos. Cada observación tiene un $ 2 / n $ probabilidad de ser un cupón, por lo que en total necesitaremos $ \ theTa (n ^ 2 \ log n) $ Observaciones Antes de recopilar todos los cupones. Si recopilamos todos los cupones, podemos ordenar el $ x $ 's; Si nos estamos perdiendo algún cupón, no podemos ordenarlos.

Las preguntas subsiguientes se reducen a los hechos sobre el problema del colector de cupones, y puede usar los límites de la cola en Wikipedia para limitar la información sobre la distribución.

Si las comparaciones se eligen sin reemplazo, entonces necesita $ \ theTa (n ^ 2) $ observaciones.

Una forma razonable de verificar si la lista es ordenable es hacer un tipo topológico, luego verifique que haya observado una comparación entre cada par de elementos adyacentes en el orden topológicamente ordenado.