Classificando com uma média de comparações

Existe um algoritmo de classificação baseado em comparação que usa uma média de comparações ?$\mathrm{lg}(n!)+o(n)$

A existência do pior algoritmo de comparação é um problema em aberto, mas o caso médio é suficiente para um algoritmo aleatório com o esperado comparações para cada entrada. O significado de é que ele é comparações do ideal, desperdiçando uma média de apenas comparações por elemento.$\mathrm{lg}(n!)+o(n)$$\mathrm{lg}(n!)+o(n)$$\mathrm{lg}(n!)+o(n)$$o(n)$$o(1)$

Como eu já tenho esse algoritmo, o incluo como resposta (usando o formato Q / A ), mas recebo respostas adicionais, incluindo outros algoritmos, se esse algoritmo já era conhecido, melhorando e pior case .l g ( n ! ) + o ( n $o(n)$$\mathrm{lg}(n!)+o(n)$

Trabalho anterior: a
classificação por mesclagem usa comparações $\mathrm{lg}(n!)+ Θ(n)$ (mesmo no pior caso).
A ordenação por inserção de mesclagem (também conhecida como ordenação Ford – Johnson) também usa comparações $\mathrm{lg}(n!)+ Θ(n)$ mas com uma constante muito menor em $Θ(n)$ .
Complexidade média aprimorada para classificação baseada em comparação (de Kazuo Iwama e Junichi Teruyama) - seu algoritmo de inserção (1,2) se assemelha a uma parte da minha resposta abaixo.

Atualização: ampliei esta resposta em um artigo Classificando com uma média de comparações$\mathrm{lg}(n!)+o(n)$ .

Sim, esse algoritmo existe. Só vou provar o , mas sob uma suposição provável de randomização, também obtemos . Também descreverei uma tentativa para e .$\mathrm{lg}(n!)+o(n)$$\mathrm{lg}(n!)+O(n^{1-ε})$$n^{0.5+o(1)}$$O(n^{0.5-ε})$

Podemos assumir que todos os elementos são distintos, anotando-os, se necessário; o caso médio usa elementos distintos em ordem aleatória. Podemos calcular o número médio de comparações adicionando a perda de entropia para cada comparação em relação ao uso de uma moeda justa.

O ponto de partida é uma espécie de inserção com uma pesquisa binária para decidir onde inserir o próximo elemento na ordenada subconjunto . Quando , uma inserção usa no máximo comparações, as quais (em termos de entropia) são ideais até um fator aditivo (e para a complexidade média dos casos, também funciona). Agora, quandonão está perto de uma potência de 2, a inserção de um elemento é abaixo do ideal (mesmo no caso médio e independentemente de como equilibramos cada consulta), mas se desperdiçar comparações, poderíamos direcionar para uma distribuição aproximadamente uniforme durante um intervalo de$S$$(1-ε)2^m ≤ |S| ≤ 2^m-1$$m$$O(ε)$$2^m ≤ |S| ≤ (1+ε) 2^m$$|S|$$A$$o(1)$$A$$S$ de comprimento próximo a uma potência de 2, obtemos a otimização desejada.

Conseguimos isso adicionando elementos em lotes e, às vezes, comparando com eficiência elementos do lote entre si, de modo que o intervalo de correspondente a um elemento diminua de maneira quase aleatória (e com a distribuição de probabilidade de dentro do intervalo) quase uniforme), e quando o comprimento do intervalo é suficientemente perto para uma potência de 2, fazendo a busca binária para inserir .$S$$A$$A$$A$

Construções comuns

Manteremos um subconjunto de elementos classificados e, para cada elemento não classificado , acompanharemos o intervalo mínimo de onde é conhecido por estar localizado. é o comprimento de ; é pela identidade dos intervalos.$S$$A$$I_A$$S$$A$$|I_A|$$I_A$$I_A=I_B$

Seja : Compare com e, em seguida, (em ordem aleatória) compare e com os elementos correspondentes de até que seus intervalos sejam separados (ou tenham o comprimento 1). O elemento é escolhido (de maneira consistente) para tornar as probabilidades da comparação o mais próximo possível de 1/2 possível, assumindo que quando é chamado, é distribuído uniformemente em . Por causa da disjunção no final, preserva a suposição de uniformidade.$\mathrm{Compare}(A,B)$$A$$B$$A$$B$$S$$S$$\mathrm{Compare}$$(A,B)$$I_A⨯I_B$$\mathrm{Compare}$

As seções a seguir podem ser lidas independentemente uma da outra.

Algoritmo A$\mathrm{lg}(n!)+o(n)$

Dado: Uma lista classificada e um lote de elementos não classificados; ; os elementos são não ordenados aleatoriamente em relação ao .$S$$m$$m∈ω(1)∩o(|S|)$$S$

Repita (1) - (3) enquanto possível:
1. Escolha dois elementos e do lote com (qualquer opção funcionará). 2. Execute . 3. Seestá perto o suficiente de uma potência de 2 ^{(nota 1)} remova do lote (sem esquecer ); e fazer da mesma forma com . Finalmente: insira todos os elementos em e complete a classificação.$A$$B$$I_A=I_B$
$\mathrm{Compare}(A,B)$
$|I_A|$$A$$I_A$$B$
$S$

Nota 1: Para "perto o suficiente", qualquer erro relativo (em função de ) funciona desde que elementos sejam removidos na etapa (4) (possível pela nota 2). Sob uma hipótese de randomização conjecturada, o uso do erro relativo captura elementos, permitindo a algoritmo de classificação média de comparação.$o(1)$$m$$m-o(m)$$c \log \log m / \log m$$m(1-\log^{-Θ(c)}m)$$\mathrm{lg}(n!)+O(n \log \log n / \log n)$

Nota 2: Como a mesma sequência de comparações leva ao mesmo intervalo de delimitação, quase todos os elementos passam pelo passo (1) vezes (a menos que sejam removidos no passo 4). No começo, se e escolhemos , comparamos contra o elemento , e cada aplicação da etapa (3) a tem probabilidade de reduçãoem vezes. Agora, para cada razão que não é uma potência racional de 2, temos , e então obtemos$Ω(\log m)$$A < B$$A$$A$$S[≈(1-1/\sqrt{2})|S|]$$A$$O(1)$$|I_A|$$≈1/(1-1/\sqrt{2})$$a>1$$∀ε>0 ∀d>0 ∃m,n∈\mathbb{N} \,\, 1-ε < \frac{a^m}{d2^n} < 1+ε$$o(n)$ limite.

Um provável algoritmo$\mathrm{lg}(n!)+O(n^{1-ε})$

Como uma hipótese de randomização, podemos obter comparações médias seguinte maneira.$\mathrm{lg}(n!)+O(n^{1-ε})$

• Aleatoriamente, embaralhe os itens e classifique a primeira metade em uma lista , mantendo a segunda metade como um lote não classificado.$S$

• Repita até que o lote esteja vazio:
  Escolha aleatoriamente . Seja . Se está vazio, remover do lote e inserção em . De outra forma:$A∈\text{batch}$$G = \{ B∈\text{batch}: |P(A < B) - 0.5| < n^{-0.51ε} \}$$G$$A$$S$
  

  1. Se houver tal que com probabilidade (diga ≥0,05), produzdentro de erro relativo de uma potência de 2, execute e se for bem-sucedido (ou seja, está dentro de erro relativo de uma potência de 2) , remover partir do lote e inserção em .$B∈G$$Θ(1)$$\mathrm{Compare}(A,B)$$|I_A|$$n^{-ε}$$\mathrm{Compare}(A,B)$$|I_A|$$n^{-ε}$$A$$S$
     
  2. Se não houver esse , execute para um aleatório .$B∈G$$\mathrm{Compare}(A,B)$$B∈G$

Se nossa suposição de randomização funcionar (ou seja, a distribuição dos comprimentos e posições dos intervalos for aleatória o suficiente), então durante grande parte do processo, um típico pode ser comparado com eficiência com uma escolha de elementos (com diferentes comprimentos de intervalo). Portanto, normalmente podemos escolher uma comparação para (1) acima e, se tivermos azar com o resultado da comparação, ainda teremos chances, alcançando (se for pequeno o suficiente, digamos 0,01) a algoritmo de comparação . Com algumas mudanças e aproximações, a computação total pode ser feita quase que linearmente: Dado um elemento$A$$n^{Θ(1)}$$n^{Θ(1)}$$Θ(\log n)$$ε$$\mathrm{lg}(n!)+O(n^{1-ε})$$A$, calcule comprimentos de intervalo promissores e procure s com os comprimentos de centro e intervalo aproximados corretos.$B$

Existem várias maneiras de otimizar as comparações, mas o obstáculo é que cada comparação pode acabar sendo azarada e temos um número limitado de comparações. Se após a otimização, fizer uma média de 4 comparações e 'for bem-sucedido' com 1/4 de probabilidade, obtemos .$\mathrm{Compare}(A,B)$$ε≈(1-ε)/4/\log_{4/3} 2 ≈ 0.09$

Uma abordagem talvez muito melhor é esperar até que um intervalo esteja próximo da potência 2, controlando não os comprimentos de intervalo individuais, mas as distribuições de comprimentos.

Uma tentativa de um algoritmo$\mathrm{lg}(n!)+n^{0.5+o(1)}$

Suponha que e recebemos um lote não classificado de elementos com os intervalos também fornecidos, comnormalmente e com distribuído uniformemente (até um erro aleatório e mantendo com precisão suficiente mesmo se condicionado em ). Em seguida, podemos classificar os itens desperdiçando uma média de comparações da seguinte forma: (*) Insira todos os elementos na ordem de suas . Dessa forma, todos os elementos são inseridos quando o comprimento do intervalo está próximo de uma potência de 2.$|S|=n$$n$$I_A$$|I_A|$$n^{1-o(1)}$$\frac{|I_A|}{2^{\lfloor \mathrm{lg} |I_A| \rfloor}}$$A < S[i]$$n^{0.5+o(1)}$
$\frac{|I_A|}{2^{\lfloor \mathrm{lg} |I_A| \rfloor}}$

O algoritmo de classificação será: Aleatoriamente embaralhar a lista e classificar o primeiro semestre . Para inserir a segunda metade, faça a distribuição correta e faça o (*) acima.$S$

Para criar o distribuição correta, podemos fazer uma distribuição 'aleatória' e, em seguida, reter a fração correta dos elementos para cada enquanto seleciona o restante aleatoriamente (repetindo se necessário). No entanto, enquanto isso deve corrigir globalmente, não sabemos se ele pode ser controlado localmente com a precisão necessária (daí a palavra "tentativa" acima).$\frac{|I_A|}{2^{\lfloor \mathrm{lg} |I_A| \rfloor}}$$|I_A|/2^{\lfloor \mathrm{lg} |I_A| \rfloor}$$\frac{|I_A|}{2^{\lfloor \mathrm{lg} |I_A| \rfloor}}$

Para fazer uma distribuição 'aleatória', podemos usar aleatoriamente com , exceto que com o inicial idêntico, não esperamos randomização em profundidade sublogarítmica (ou seja, com tempo suficiente). No entanto, suponho que obtemos randomização em uma profundidade sublogarítmica usando generalizações (provavelmente qualquer escolha razoável funcionará) de com elementos: Se mantivermos elementos entrelaçados (isto é, ligados através de resultados de comparação), que deve ter cerca de escolhas noncommuting para cada comparação com . Isso deve permitir$\mathrm{Compare}(A,B)$$P(A < B)≈0.5$$I_A$$I_A$$\mathrm{Compare}$$k=ω(1)$$k=ω(1)$$k$$S$$O(\log_k n + \log k)$profundidade de randomização, conforme desejado (assumindo que não seja muito grande, pois precisamos de profundidade para separar os elementos). Espero que a computação possa ser feita quase-linearmente, se usar um suficientemente pequeno .$k$$Θ(\log k)$$k$

Como uma comparação com probabilidade sim desperdiça apenas entropia, a randomização inicial e a ligeira não uniformidade dos elementos em seus intervalos delimitadores só precisam de resíduos de entropia. Se a formatação da distribuição for bem-sucedida, o desperdício de entropia decorre principalmente de incompatibilidades de comprimento de intervalo durante (*) (daí o ).$1/2+n^{-0.5}$$O(1/n)$$n^{o(1)}$$n^{0.5+o(1)}$

Uma combinação possível :$\mathrm{lg}(n!)+O(n^{0.5-ε})$ Se a configuração da distribuição funcionar bem o suficiente e tornarmos o tamanho do lote igual e rejeitando seletivamente elementos em (*) (acima), podemos inserir todos, exceto esses elementos com resíduos de entropia seguinte maneira. Divida em intervalos quase iguais e, durante a inserção, se estabelece em um intervalo, rejeite (ou seja, cancele a inserção) se o intervalo for muito longo, reduzindo assim a variação nos comprimentos desses intervalos$|S|+n^{0.5+ε}$$≈n^{0.5+ε}$$≈n^{0.5+ε}$$n^{0.5-ε/2+o(1)}$$S$$n^ε$$I_A$$Θ(n^{ε/2})$vezes, o que reduz as variações de comprimento aleatório intervalos em vezes, conforme necessário. Agora, podemos usar o algoritmo para inserir os elementos restantes com o desperdício se for pequeno o suficiente.$n^{1-o(1)}$$n^{ε/2-o(1)}$$\mathrm{lg}(n!)+O(n^{1-ε})$$O(n^{0.5-ε'})$$ε$

Complexidade de classificação no pior caso: provavelmente, existe um algoritmo de classificação com comparações no pior caso. Para encontrar mediana, existe um gap linear entre a média de casos ( ) e o pior caso (pelo menos ). No entanto, para classificação, há bastante liberdade para organizar comparações e para encontrar novos algoritmos de classificação.$\mathrm{lg}(n!)+o(n)$$1.5n+o(n)$$(2+ε)n-O(1)$