Se eu andar a lista e excluir todos os elementos fora de ordem, deva-me, em média quantos elementos serão deixados?

Question

Eu tenho uma lista uniformemente permutada aleatoriamente de comprimento $ n $ . Eu ando através da lista elemento-por-elemento e exclui um elemento se estiver fora de ordem (comparado aos elementos anteriores no pedido da lista). O que eu sou deixado é uma lista mais curta que é garantida para ser em ordem.

Exemplo: os elementos estrelados desta lista seriam excluídos durante a caminhada.

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

Minha pergunta é: em média, qual será o comprimento da lista restante? E há alguma forma simples / óbvia da distribuição deste?

e como um acompanhamento: Se usássemos isso para um algoritmo de classificação (chamado Grupo), qual seria o tempo de execução? Para ser claro, o algoritmo seria algo assim: $$ \ textit {dropsort} (\ text})=textit {mesclar} (\ text}, \ textit} (\ texto} lista} )) $$

Esta questão foi inspirada por esta r / programmerhumor post .

Answer 1

Você pode calcular a média usando linearidade de expectativa.

Deixe a variável aleatória $ x $ denotam o número de elementos que são retidos. Deixe $ x_i $ ser um indicador r.v. Isso é 1 se a $ i $ th elemento é retido, ou 0 caso contrário. Então $ x= x_1 + \ Dots + x_n $ , então

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

Agora a $ i $ th elemento é retido se e somente se for o maior número entre a primeira $ i $ elementos na lista. Portanto, $ \ pr [x_i= 1]=frac {1} {i} $ , então

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

Em outras palavras, o comprimento médio da lista restante é $ o (\ log n) $ .

Eu não sei qual é a distribuição.

Como heurística, o tempo de execução esperado de gota satisfaria uma recorrência algo como $ t (n) \ APROX T (N- \ LOG (n)) + O (n)) + n) $ , que corresponde à $ o \ left (\ frac {n ^ 2} {\ log n} \ direito) $ tempo. .