Esta é uma tradução automática, sendo a versão em inglês a original. Ler o original
Porque é que a ordenação não pode ser mais rápida
Ordenar cem coisas exige pelo menos 525 comparações. Não com os algoritmos de hoje. Nunca.
A maioria das afirmações sobre desempenho são afirmações sobre um programa em particular. Esta não o é. Diz que nenhum algoritmo de ordenação por comparação, escrito por quem quer que seja, em qualquer linguagem, em qualquer hardware que ainda não tenha sido inventado, consegue ordenar cem itens em menos de 525 comparações.
O argumento nunca analisa um algoritmo.
Contar os destinos, não os passos
Uma lista de n itens distintos pode ser disposta em n! ordens. Exatamente uma delas está ordenada e, antes de começar, não faz a mínima ideia de qual tem nas mãos.
Considere agora o que uma comparação lhe dá. Pergunta se a vem antes de b e recebe como resposta sim ou não. Um bit. Seja o que for que o seu algoritmo faça a seguir, fá-lo sabendo mais um facto binário do que antes.
Assim, após c comparações, recebeu c bits, e c bits podem distinguir, no máximo, 2c situações diferentes. Para ter a certeza de identificar qual das n! disposições tinha no início, necessita de
2c ≥ n!, ou seja, c ≥ log₂(n!).
Eis a demonstração completa. Não contém ciclos, não contém recursão e não faz qualquer suposição sobre a estratégia, e é precisamente por isso que se aplica a algoritmos em que ainda ninguém pensou.
O nome consagrado para isto é o limite da árvore de decisão. Imagine qualquer ordenação por comparação como uma árvore: cada nó interno é uma comparação, cada ramo é uma das duas respostas e cada folha é uma disposição possível. Uma árvore de profundidade c tem, no máximo, 2c folhas, e a árvore deve ter pelo menos n! delas, pelo que a sua profundidade é de pelo menos log₂(n!). A profundidade é o número de comparações no pior caso.
Quais são na realidade os números
Doze itens podem ser dispostos de 479,001,600 maneiras. O logaritmo desse número é 28,84, pelo que doze itens necessitam de pelo menos 29 comparações. Cem itens necessitam de pelo menos 525. Um milhão necessita de pelo menos 18,488,885.
Abra o Big-O Complexity Explorer e leia a linha para N = 100. A coluna O(N log N) indica 664, situando-se entre O(N) a 100 e O(N²) a 10,000. Esse 664 é N × log₂N, a taxa de crescimento que consideramos ótima para a ordenação.
Mas o limite mínimo é 525, e 664 está 26,6% acima desse valor.
A diferença não se deve a falta de rigor da ferramenta. log₂(n!) não é exatamente n log₂ n: a aproximação de Stirling fornece n log₂ n − 1,4427n, e para N = 100 essa correção equivale a 139 comparações. Assim, "N log N" identifica a forma correta, mas sobrestima o custo real por um fator constante do tamanho da entrada. A forma é o que subsiste à medida que N cresce; os 139 são o que notaria se contasse efetivamente.
A saída que não é uma brecha
O Counting sort ordenará um milhão de inteiros pequenos em muito menos de 18 milhões de operações, sem contradizer uma única palavra do que foi dito acima.
A demonstração pressupõe que cada pergunta feita é uma comparação. O Counting sort faz um tipo de pergunta diferente: lê uma chave e usa-a como um endereço. Isso extrai muito mais do que um bit de cada vez, porque explora algo que o modelo de comparação recusa pressupor: nomeadamente, que as chaves são inteiros pequenos cujo interior é permitido inspecionar.
Este é o hábito útil. Um limite inferior é sempre um limite inferior dentro de um modelo, e quando um resultado parece ter sido superado, o modelo foi alterado. O Sorting Race executa os algoritmos baseados em comparação uns contra os outros, e o que os separa são fatores constantes e o comportamento da memória, e não o expoente. Estão todos limitados inferiormente pelos mesmos 525.
Onde já se deparou com isto antes
Se a estratégia da contagem lhe parece familiar, é a mesma que está por trás da razão pela qual nenhum compressor consegue reduzir todos os ficheiros. Aí, a contagem era de ficheiros possíveis contra ficheiros mais curtos possíveis; aqui, é de disposições possíveis contra sequências de resposta possíveis. Ambas as demonstrações funcionam ao notar que um conjunto de resultados é maior do que o conjunto de coisas que os poderiam descrever.
O Entropy Coding é a mesma quantidade sob a outra perspetiva: o número de bits de que realmente necessita é determinado por quantas possibilidades restam, e nenhuma codificação o consegue superar.
Nenhum dos resultados lhe diz como escrever um programa rápido. Dizem-lhe quando deve parar de procurar um.