Ordenar a comparação
| n | log log 2 (n ! ) ⌉ {\displaystyle \left\iceil \log _{2} (n!)\right\rceil }
|
Mínimo |
|---|---|---|
| 1 | 0 | 0 |
| 2 | 1 | 1 |
| 3 | 3 | 3 |
| 4 | 5 | 5 |
| 5 | 7 | 7 |
| 6 | 10 | 10 |
| 7 | 13 | 13 |
| 8 | 16 | 16 |
| 9 | 19 | 19 |
| 10 | 22 | 22 |
| 11 | 26 | 26 |
| 12 | 29 | 30 |
| 13 | 33 | 34 |
| 14 | 37 | 38 |
| 15 | 41 | 42 |
| 16 | 45 | 45 ou 46 |
| 17 | 49 | 49 ou 50 |
| 18 | 53 | 53 ou 54 |
| 19 | 57 | 58 |
| 20 | 62 | 62 |
| 21 | 66 | 66 |
| 22 | 70 | 71 |
| n | ⌈ log 2 ( n ! ) ⌉ {\displaystyle \left\iceil \log _{2} (n!)\right\rceil }
|
n log 2 n − n ln 2 {\displaystyle n\log _{2}n{\frac {n}{\ln 2}}}
 |
| 10 | 22 | 19 |
| 100 | 525 | 521 |
| 1 000 | 8 530 | 8 524 |
| 10 000 | 118 459 | 118 451 |
| 100 000 | 1 516 705 | 1 516 695 |
| 1 000 000 | 18 488 885 | 18 488 874 |
to the real minimum number of comparisons (from OEIS: a036604) required to sort a list of N items (for the worst case). Abaixo: a Utilização de Stirling, da aproximação, este limite inferior é bem aproximada por n log 2 n − n ln 2 {\displaystyle n\log _{2}n{\frac {n}{\ln 2}}}
.
O número de comparações que uma comparação algoritmo de ordenação requer aumenta em proporção ao n log ( n ) {\displaystyle n\log(n)}
, onde n {\displaystyle n}
é o número de elementos a ordenar. Esta ligação é assintoticamente apertada.
dada uma lista de números distintos( podemos assumir isso porque esta é uma análise do pior caso), há permutações n factorial exatamente uma das quais é a lista em ordem ordenada. The sort algorithm must gain enough information from the comparisions to identify the correct permutation. Se o algoritmo sempre completa após no máximo passos f(n), Ele não pode distinguir mais de 2F(n) Casos porque as chaves são distintas e cada comparação tem apenas dois resultados possíveis. Portanto,
2 f (n ) ≥ n ! {\displaystyle 2^{f (n)}\geq n!}
, ou equivalentemente f (n ) ≥ log 2 (n ! ) . {\displaystyle f(n)\geq \log _{2} (n!).}
olhando para o primeiro n / 2 {\displaystyle n/2}
factores de n ! = n (n − 1 ) ⋯ 1 {\displaystyle n!= n (n-1)\cdots 1}
, obtemos log 2 (n ! ) ≥ log 2 ((n 2 ) n 2 ) = n 2 log log n log log 2 − n 2 = Θ (n log n ) . {\displaystyle \log _{2}(n!)\geq \log _{2}\left(\left({\frac {n}{2}}\right)^{\frac {n}{2}}\right)={\frac {n}{2}}{\frac {\log n}{\log 2}}-{\frac {n}{2}}=\Theta (n\n log n).
log 2 ( n ! ) = Ω ( n log n ) . {\displaystyle \log _{2}(n!) = \Omega (n\log n).
isto proporciona a parte inferior da alegação. Uma melhor ligação pode ser dada através da aproximação de Stirling.
um limite superior idêntico resulta da existência dos algoritmos que atingem este limite no pior dos casos, como heapsort e mescla.
the above argument provides an absolute, rather than only asymptotic lower bound on the number of comparisons, namely ⌈ log 2 (n ! ) ⌉ {\displaystyle \left\iceil \log _{2} (n!) \direita\rceil }
comparações. Este limite inferior é bastante bom (pode ser abordado dentro de uma tolerância linear por um simples tipo de junção), mas é conhecido por ser inexato. Por exemplo, ⌈ log 2! (13! ) ⌉ = 33 {\displaystyle \left\lceil \log _{2} (13!) \direita\rceil =33}
, mas o número mínimo de comparações para classificar 13 elementos foi provado ser 34.
determinar o número exato de comparações necessárias para classificar um dado número de entradas é um problema computacionalmente difícil mesmo para n pequeno, e nenhuma fórmula simples para a solução é conhecida. Para alguns dos poucos valores concretos que foram computados, veja OEIS: A036604.
limite inferior para o número médio de comparisonsEdit
um limite semelhante aplica-se ao número médio de comparações. Supondo que a
- todas as chaves são distintos, i.e. cada comparação dará uma>b ou a<b,
- a entrada é uma permutação aleatória, escolhida uniformemente a partir do conjunto de todas as possíveis permutações de n elementos,
é impossível determinar qual a ordem em que a entrada é no com menos de log2(n!) comparações em média.
isto pode ser mais facilmente visto usando conceitos da teoria da informação. A entropia de Shannon de tal permutação aleatória é log2 (n!) partes. Uma vez que uma comparação pode dar apenas dois resultados, a quantidade máxima de informação que fornece é de 1 bit. Portanto, após K comparações, a Entropia restante da permutação, dado os resultados dessas comparações, é pelo menos log2 (n!)- K bits em média. Para realizar a ordenação, é necessária informação completa, de modo que a Entropia restante deve ser 0. Segue-se que k deve ser pelo menos log2 (n!) em média.
The lower bound derived via information theory is phrased as ‘information-theoretic lower bound’. O limite inferior teórico da informação é correto, mas não é necessariamente o limite inferior mais forte. E em alguns casos, o limite inferior teórico da informação de um problema pode até estar longe do verdadeiro limite inferior. Por exemplo, as informações teórico-limite inferior de seleção é ⌈ log 2 ( n ) ⌉ {\displaystyle \left\lceil \log _{2}(n)\right\rceil }
considerando que n − 1 {\displaystyle n-1}
comparações são necessárias para que um argumento contraditório. The interplay between information-theoretic lower bound and the true lower bound are much like a real-valued function lower-bounding an integer function. No entanto, isto não é exatamente correto quando o caso médio é considerado.
para descobrir o que acontece ao analisar o caso médio, a chave é a que se refere a “média”? Média sobre o quê? With some knowledge of information theory, the information-theoretic lower bound averages over the set of all permutations as a whole. Mas qualquer algoritmo de computador (sob o que se acredita atualmente) deve tratar cada permutação como uma instância individual do problema. Por isso, o limite inferior médio que procuramos é calculado em relação a todos os casos individuais.
para procurar o limite inferior relacionado com a não-realizabilidade dos computadores, adotamos o modelo Árvore de decisão. Vamos reformular um pouco do nosso objectivo. No modelo da árvore de decisão, o limite inferior a ser mostrado é o limite inferior do comprimento médio dos caminhos raiz-a-folha de um n ! displaystyle n!}
– folha (na qual cada folha corresponde a uma permutação). Seria convencido a dizer que uma árvore binária completa equilibrada atinge o mínimo do comprimento médio. Com alguns cálculos cuidadosos, para uma árvore binária completa balanceada com n ! displaystyle n!
folhas, o comprimento médio dos caminhos raiz-folha é dado por ( 2 n ! – 2 log log 2 !n! Log + 1) log log 2 !n! ⌉ + (2 log log 2 !n! ⌋ + 1 – n ! ) log log 2 !n! não ! {\displaystyle {\frac {(2n!-2^{\lfloor \log _{2}n!\rfloor +1})\cdot \ikeil \log _{2}n!\rceil +(2^{\lfloor \log _{2}n!\rfloor +1} – n!)\cdot \lfloor \log _{2}n!\rfloor }{n!}}}
por exemplo, para n = 3, o limite inferior teórico da informação para o caso médio é Aproximadamente 2.58, enquanto o limite inferior médio derivado através do modelo de árvore de decisão é 8/3, Aproximadamente 2.67.
no caso Em que vários itens podem ter a mesma chave, não é óbvio estatística interpretação para o termo “caso médio”, portanto, um argumento como o acima não pode ser aplicada sem fazer suposições específicas sobre a distribuição de chaves.
