Any decent algorithms textbook will explain how fast sorting algorithms like quicksort and heapsort are, but itdoesn’t take crazy maths to prove that they are as asymptotically fast as you can get.
Uma nota pedante sobre notação
A maioria dos cientistas informáticos usa a notação big-O para significar “assimmptoticamente igual, até um factor de escala constante”, o que não é bem o que significa para outros matemáticos. Desculpe, vou usar big-O como nos livros de texto de CS, mas pelo menos não vou misturar com outra notação matemática.
Seleção baseada em comparação
Vejamos o caso especial dos algoritmos que comparam valores dois de cada vez (como quicksort e heapsort, e a maioria dos outros algoritmos populares). As idéias podem ser estendidas a todos os algoritmos de ordenação mais tarde.
Um simples argumento de contagem para o pior caso
Suponha que você tenha um array de quatro elementos, todos diferentes, em ordem aleatória. Você pode ordenar comparando apenas os elementos? Obviamente não, mas aqui está uma boa razão que prova que você não pode: Por definição, para ordenar o array, você precisa de como reorganizar os elementos para colocá-los em ordem. Em outras palavras, você precisa saber qual permutação é necessária. Quantas permutações possíveis existem? O primeiro elemento pode ser movido para um dos quatro lugares, o segundo elemento pode ir para um dos três restantes, o terceiro elemento tem duas opções, e o último elemento tem de ocupar o único lugar. Portanto, há 4×3×2×1=4!=244 {\i1}vezes 3 {\i1}vezes 2 {\i1}vezes 1 = 4! = 24 possíveis permutações à escolha, mas há apenas dois resultados possíveis de comparar duas coisas diferentes: “BIGGER” e “SMALLER”. Se você fez uma lista de todas as permutações possíveis, você pode decidir que “BIGGER” significa que você precisa da permutação #8 e “SMALLER” significa que você precisa da permutação #24, mas não há como você saber quando você precisa das outras 22 permutações.
Com duas comparações, você tem 2×2=42 \ vezes 2 = 4 saídas possíveis, o que ainda não é suficiente. Você não pode ordenar todas as possíveis permutações, a menos que você faça pelo menos cinco comparações (25=322^5 = 32). Se W(N)W(N) é o pior número de comparações necessárias para ordenar NN elementos diferentes usando algum algoritmo, podemos dizer
2W(N)≥N!2^{W(N)} \geq N!
Tomando uma base logarítmica 2,
W(N)≥log2N!W(N) \geq \geq \log_2{N!}
Aymptotically, N!N! cresce como NNN^N (veja também a fórmula de Stirling), então
W(N)⪰logNNN=NlogNW(N) \succeq \log{N^N} = N\log{N}
E isso é um limite O(NlogN)O(N\log N) no pior dos casos só de contar as saídas.
Médio caso da teoria da informação
Podemos obter um resultado mais forte se estendermos esse argumento de contagem com um pouco de teoria da informação. Aqui está como poderíamos usar um algoritmo de ordenação como código para transmitir informação:
- Eu penso num número – digamos, 15
- Eu procuro a permutação #15 da lista de permutações de quatro elementos
- Eu corro o algoritmo de ordenação nesta permutação e registo todos os resultados da comparação “BIGGER” e “SMALLER”
- Transmito-lhe os resultados da comparação em código binário
- Você reencena o meu algoritmo de ordenação executado, passo a passo, referindo-se à minha lista de resultados de comparação conforme necessário
- Agora você sabe como rearranjei meu array para fazer a ordenação, você pode reverter a permutação para descobrir meu arrayoriginal
- Você procura meu array original na lista de permutação para descobrir que eu transmiti o número 15
Okay, é um pouco estranho, mas poderia ser feito. Isso significa que os algoritmos de ordenação são vinculados pelas mesmas leis de codificação normalizada, incluindo o teorema que prova que não há um compressor de dados universal. Eu transmiti um bit de percomparação que o algoritmo faz, então, em média, o número de comparações deve ser pelo menos o número de bits necessários para rasgar meus dados, de acordo com a teoria da informação. Mais tecnicamente, o número médio de comparações deve ser pelo menos a entropia de Shannon dos meus dados de entrada, medidos em bits. A entropia é uma medida matemática do conteúdo de informação, ou imprevisibilidade, de algo.
Se eu tiver um array de elementos NN que poderiam estar em qualquer ordem possível sem viés, então a entropia é maximizada e islog2N!\log_2{N!} bits. Isso prova que O(NlogN)O(N\log{N}) é uma média ótima para uma ordenação baseada em comparação com entrada arbitrária.
Essa é a teoria, mas como os algoritmos de ordenação reais se comparam? Abaixo está um gráfico do número médio de comparações necessárias para ordenar um array. Eu comparei o ótimo teórico contra a quicksort ingênua e o tipo de fusão-inserção Ford-Johnson, que foi projetado para fazer comparações tominimizadas (embora raramente seja mais rápido que a quicksort em geral, porque há mais na vida do que minimizar as comparações). Desde que foi desenvolvido em 1959, o tipo merge-insertion foi ajustado para espremer mais algumas comparações, mas a trama mostra que já é quase ideal.
É bom quando uma pequena teoria dá um resultado prático tão apertado.
Sumário até agora
Aqui está o que foi provado até agora:
- Se o array poderia começar em qualquer ordem, pelo menos O(NlogN)O(N\log{N}) comparações são necessárias no pior caso
- O número médio de comparações deve ser pelo menos a entropia do array, que é O(NlogN)O(N\log{N}) para entrada aleatória
Nota que #2 permite que algoritmos de ordenação baseados em comparação sejam mais rápidos que O(NlogN)O(N\log{N}) se a entrada for de baixa entropia (em outras palavras, mais previsíveis). Merge sort é próximo de O(N)O(N) se o input contém muitas subarrays ordenadas. Inserir sort é próximo de O(N)O(N) se o input é um array que foi ordenado antes de ser um pouco perturbado. Nenhum deles bate O(N)O(N)O(N\log{N}) no pior caso a menos que algumas ordenações de array sejam impossíveis como inputs.
General sorting algorithms
Comparison-based sorts são um caso especial interessante na prática, mas não há nada teoricamente especial sobreCMP ao contrário de qualquer outra instrução em um computador. Ambos os argumentos acima podem ser generalizados para qualquer algoritmo de ordenação se você observar algumas coisas:
- A maioria das instruções do computador tem mais de duas saídas possíveis, mas ainda tem um número limitado
- O número limitado de saídas significa que uma instrução só pode processar uma quantidade limitada de entropia
Que nos dá o mesmo O(NlogN)O(N\log{N}) limite inferior no número de instruções. Qualquer computador fisicamente realizável só pode processar o número alimentado de instruções de cada vez, então isso é um limite inferior de O(NlogN)O(N\log{N}) no tempo necessário, também.
Mas e os algoritmos “mais rápidos”?
A implicação prática mais útil do limite geral de O(NlogN)O(N\log{N}) é que se você ouvir falar sobre qualquer algoritmo assimptóticamente mais rápido, você sabe que ele deve ser “trapaceiro” de alguma forma. Deve haver algum truque que signifique que não é um algoritmo de ordenação de propósito geral que se escalona para arbitrarilylarge arrays. Pode ainda ser um algoritmo útil, mas é uma boa ideia ler as letras miúdas de perto.
Um exemplo bem conhecido é o radix sort. É frequentemente chamado um algoritmo de ordenação O(N)O(N), mas o senão é que só funciona se todos os números caberem em kk bits, e é realmente O(kN)O(kN).
O que isso significa na prática? Suponha que você tenha uma máquina de 8 bits. Você pode representar 28=2562^8 = 256 números diferentes em 8 bits, então se você tem um array de milhares de números, você vai ter duplicatas. Isso pode ser bom para algumas aplicações, mas para outras você precisa atualizar para pelo menos 16 bits, o que pode representar 216=65,5362^16 = 65,536 números de forma distinta. 32 bits irão suportar 232=4,294,967,2962^32 = 4,294,967,296 números diferentes. Conforme o tamanho do array vai aumentando, o número de bits necessários tenderá a subir também. Para representar NN números diferentes distintamente, você precisará de k≥log2Nk \geq \log_2{N}. Então, a menos que você esteja bem com muitas duplicatas no seu array, O(kN)O(kN) é efetivamente O(NlogN)O(N\log{N}).
A necessidade de O(NlogN)O(N\log{N}) de dados de entrada no caso geral realmente prova o resultado geral por si só. Esse argumento não é tão interessante na prática porque raramente precisamos ordenar bilhões de inteiros em uma máquina de 32 bits, e se alguém atingiu os limites de uma máquina de 64 bits, eles não contaram para o resto de nós.