Dada uma lista aberta de $ n $ itens, quantas comparações aleatórias são necessárias em média para ser capaz de classificar a lista?

Question

Há uma lista antiderrapante de $ n $ Itens $ x_1, \ ldots, x_n $ . Até você pode classificar a lista, você receberá uma das $ {n \ escolher 2} $ comparações binárias possíveis uniformemente a aleatoriamente (com substituição).

Em média, quantas dessas comparações aleatórias você precisará ser capaz de classificar a lista?

Algumas perguntas de acompanhamento:

.
1. O que a distribuição para o número de comparações necessárias é semelhante?
2. Qual é a resposta se você usar $ k $ comparações caras em vez de binários.
3. Qual é a resposta se as comparações forem feitas sem substituição (isto é, você não obterá a mesma comparação duas vezes)?
4. Dado um conjunto de comparações, como se pode verificar se a lista é classificada? Estou quase certo de que a resposta é construir uma deg e tipo topológica, mas eu só quero confirmar.

Uma resposta exata-ish seria legal, mas uma grande $ O $ Resposta é bom também, suponho.

Answer 1

Assimpoticamente, você precisará $ \ theta (n ^ 2 \ log n) $ comparações.

Suponha $ x _ {(1)}, \ pontos, x _ {(n)} $ denota os elementos em ordem classificada. Então, se você não vê uma comparação entre $ x _ {(1)} $ e $ x _ {(2)} $ , você não terá como dizer qual ordem eles devem aparecer. O mesmo é verdadeiro de todos os pares de elemento adjacente. Assim, existem cupons de $ N-1 $ (um por par adjacente de elementos), e você precisa coletar todos eles. Baseado no problema coletor de cupom , sabemos que você precisa $ \ theta (n \ log n) $ cupons escolhidos aleatoriamente antes de recolher todos eles. Cada observação tem uma $ 2 / N $ chance de ser um cupom, então no total, precisaremos $ \ theta (n ^ 2 \ log n) $ observações antes de coletamos todos os cupons. Se coletarmos todos os cupons, podemos classificar a $ x $ 's; Se estamos perdendo algum cupom, não podemos resolvê-los.

As perguntas subseqüentes resumem os fatos sobre o problema do coletor de cupom, e você pode usar os limites da cauda na Wikipedia para vincular as informações sobre a distribuição.

Se comparações forem escolhidas sem substituição, então você precisa $ \ theta (n ^ 2) $ observações.

Uma maneira razoável de verificar se a lista é classificável é fazer um tipo topológico, então verifique se você observou uma comparação entre todos os pares de itens adjacentes na ordem Topologicamente Classificada.