Ordinamento online senza modifiche

Question

C'è un array con $ n $ posti. C'è un flusso di numeri unici $ n $ che arrivano a un ordine casuale (permutazione selezionata in modo uniforme a caso).

Ogni volta che arriva un numero, dobbiamo metterlo da qualche parte nell'array e non ci è permesso di spostarlo in seguito. L'obiettivo è avere il maggior numero possibile di numeri (in attesa) nella loro posizione corretta nell'array finale. La "posizione corretta" è definita come la posizione in cui sembrerebbe se i numeri fossero stati ordinati.

Cosa si sa di questo problema? Qual è il miglior tasso di successo atteso e quale algoritmo lo raggiunge?

_Appunti:

• _{Una domanda correlata è: Qual è l'algoritmo di smistamento online più veloce? . Discute una situazione in cui gli articoli possono essere spostati quando arrivano nuovi articoli e l'obiettivo è ridurre al minimo il tempo di esecuzione.}

• _{Sono principalmente interessato a massimizzare il numero previsto delle posizioni corrette. Tuttavia, è anche interessante se esiste un modo per migliorare la probabilità che tutti i numeri siano nella posizione corretta, sopra O (1/N!)}