Dato un elenco nonto di $ N $ articoli, quanti confronti casuali sono necessari in media per poter ordinare la lista?

Question

C'è un elenco non esto da $ N $ elementi $ x_1, \ ldots, x_n $ . Fino a quando non è possibile ordinare l'elenco, ti viene assegnato una delle $ {n \ Scegli 2} $ Possibili confronti binari uniformemente a caso (con la sostituzione).

In media, quanti di questi confronti casuali dovranno essere in grado di ordinare la lista?

Alcune domande di follow-up:

.
1. A cosa serve la distribuzione per il numero di confronti del numero di confronti?
2. Qual è la risposta se usi $ k $ Confronti invece di quelli binari.
3. Qual è la risposta se i confronti sono fatti senza sostituzione (cioè non otterrai lo stesso confronto due volte)?
4. Dato un insieme di confronti, come si può verificare se l'elenco è ordinato? Sono quasi certo che la risposta è costruire un tipo dag e topologico, ma voglio solo confermare.

Una risposta esatta-ish sarebbe bella, ma una grande $ o $ risposta è anche fine, suppongo.

Answer 1

Assompoticamente, avrai bisogno di $ \ theta (n ^ 2 \ log n) $ confronti.

Supponiamo $ x _ {(1)}, \ Dots, x _ {(n)} $ indica gli elementi in ordine ordinato. Quindi se non vedi un confronto tra $ x _ {(1)} $ e $ x _ {(2)} $ , non avrai alcun modo di dire quale ordine dovrebbe apparire. Lo stesso vale per ogni coppia di elementi adiacenti. Quindi, ci sono $ N-1 $ coupon (uno per paio di elementi adiacenti), e devi raccoglierli tutti. Basato su Coupon Collector problem , sappiamo che avrai bisogno di $ \ theta (n \ log n) $ Coupon scelti a caso prima che li abbiamo raccolti tutti. Ogni osservazione ha una classe $ 2 / N $ possibilità di essere un coupon, quindi in totale avremo bisogno di $ \ theta (n ^ 2 \ log n) $ osservazioni prima di aver raccolto tutti i coupon. Se raccogliamo tutti i coupon, possiamo ordinare la $ x $ 's; Se ci manca un coupon, non possiamo ordinarli.

Le domande successive decorassero i fatti sul problema del collettore del coupon e puoi utilizzare i limiti di coda su Wikipedia per vincolare le informazioni sulla distribuzione.

Se i confronti vengono scelti senza sostituzione, è necessario $ \ Theta (n ^ 2) $ Osservazioni.

Un modo ragionevole per verificare se l'elenco è ordinabile è quello di fare un tipo topologico, quindi verificare di aver osservato un confronto tra ogni coppia di elementi adiacenti nell'ordine ordinato topologicamente.