Se você está vendo esta mensagem, significa que estamos tendo problemas para carregar recursos externos em nosso website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Conteúdo principal

Análise do quicksort

Como é que os tempos de ordenação rápida no pior caso e no caso médio se diferencião? Vamos começar observando o tempo do pior caso. Vamos supor que somos muito azarados e que o tamanho das partições não estão balanceadas. Em particular, supomos que o pivô escolhido pela função partição é sempre o menor ou o maior elemento no n-subarranjo. Então uma das partições não irá conter elementos e a outra partição irá conter n1 elementos—tudos menos o pivô. Então a chamada recursiva será no subarranjo de tamanhos 0 e n1.
Como no tipo de mesclagem, o tempo para uma determinada chamada recursiva em um subarranjo de elemento n é Θ(n). Na mesclagem, que era o tempo para mesclagem, mas em ordenação rápida é o tempo para particionamento.

Tempo de execução no pior caso

Quando a ordenação rápida tem sempre as partições o mais desbalanceada possível, então a chamada original leva tempo cn para alguma constante c, a chamada recursiva sobre n1 elementos leva c(n1) de tempo, a chamada recusiva sobre n2 elementos leva c(n2) de tempo, e assim por diante. Aqui está uma árvore do tamanho do sub problema com seus tempos de particionamento:
Quando nós particionamos todos os níveis, nós temos
cn+c(n1)+c(n2)++2c=c(n+(n1)+(n2)++2)=c((n+1)(n/2)1) .
A última linha é por causa da série aritmética 1+2+3++n, como nós vimos quando nós analizamos mesclagem selecionada. (Nós subtraimos 1 porque a organização, o somatório começa em 2, não em 1.) Nós temos alguns termos de baixa ordem e coeficientes constantes, mas quando usamos a notação big-Θ, nós ignoramos eles. Na notação big-Θ, a ordenação rápida do pior caso roda com tempo de Θ(n2).

Tempo de execução no melhor caso

O melhor caso da ordenação rápida ocorre qunado as partições estão muito bem balanceadas: os seus tamanhos são iguais ou até 1 de cada uma. O primeiro caso ocorre se o subarranjo tem um número ímpar de elementos e o pivô está no meio depois do particionamento e ainda cada partição tem (n1)/2 elementos. O último caso ocorre se o subarranjo tem um número par de elementos n e uma partição tem n/2 elementos com a outra tendo n/21. Em ambos os casos, cada partição tem no máximo n/2 elementos, e a árvore do tamanho do subproblema parece a árvore do subproblema do um tipo fundir de mesclagem, com as partições de tempo parecendo fundir com o tempo:
Usando a notação big-Θ, nós temos o mesmo resultado obtido para o merge sort: Θ(nlog2n).

Tempo de execução médio

A demonstração de que o tempo de execução médio também é Θ(nlog2n) exige matemática mais avançada e, portanto, não vamos por esse caminho. Porém, podemos ter uma boa intuição olhando para alguns outros casos para entender por que o tempo é O(nlog2n). (Como temos O(nlog2n), o limite Θ(nlog2n) se mantém porque o tempo do caso médio não pode ser melhor que o tempo de execução no melhor caso). Primeiro, vamos imaginar que não recebemos sempre partições balanceadas, mas que recebemos, no pior caso, uma divisão 3-para-1. Ou seja, imagine que cada vez que particionamos, um lado tem 3n/4 elementos e o outro lado tem n/4. (Para simplificar os cálculos, não vamos nos preocupar com o pivô). Então, a árvore do tamanho do subproblema e o tempo de particionamento ficariam assim:
The left child of each node represents a subproblem size 1/4 as large, and the right child represents a subproblem size 3/4 as large. Since the smaller subproblems are on the left, by following a path of left children, we get from the root down to a subproblem size of 1 faster than along any other path. As the figure shows, after log4n levels, we get down to a subproblem size of 1. Por que log4n níveis? It might be easiest to think in terms of starting with a subproblem size of 1 and multiplying it by 4 until we reach n. In other words, we're asking for what value of x is 4x=n? The answer is log4n. How about going down a path of right children? The figure shows that it takes log4/3n levels to get down to a subproblem of size 1. Por que log4/3n níveis? Since each right child is 3/4 of the size of the node above it (its parent node), each parent is 4/3 times the size of its right child. Let's again think of starting with a subproblem of size 1 and multiplying the size by 4/3 until we reach n. For what value of x is (4/3)x=n? The answer is log4/3n.
Em cada um dos primeiros log4n níveis, há n elementos (novamente, incluindo pivôs que na realidade não estão mais sendo particionados), e assim o tempo total de particionamento para cada um desses níveis é cn. Mas e o resto dos níveis? Cada um tem menos de n nós, e assim o tempo de particionamento para todos os níveis é de no máximo cn. Ao todo, existem log4/3n níveis e, portanto, o tempo total de particionamento é O(nlog4/3n). Agora, há um fato matemático que nos mostra que
logan=logbnlogba
para todos os números positivos a, b, e n. Deixando a=4/3 e b=2, nós temos que
log4/3n=log2nlog2(4/3) ,
e, portanto, log4/3n e log2n se diferenciam apenas por um fator de log2(4/3), que é constante. Como fatores constantes não importam quando utilizamos a notação big-O, podemos dizer que se todas as divisões são 3-para-1, então o tempo de execução do quick sort é O(nlog2n), embora com um fator constante oculto maior que o tempo de melhor caso.
Com que frequência devemos esperar ver a divisão 3-para-1 ou melhor? Depende de como escolhemos o pivô. Vamos imaginar que o pivô tem a mesma chance de aparecer em qualquer lugar entre o elemento n- do subarranjo depois de particionado. Então para pegar uma divisão que é 3-para-1 ou melhor, o pivô deveria estar em algum lugar no "meio da metade":
Então, se o pivô é igual a probabilidade de parar em qualquer lugar no subarranjo depois de particionado, há uma chance de 50% de pegar a pior divisão 3-para-1. Em outras palavras, nós esperamos a divisão de 3-para-1 ou melhor por metade do tempo.
O outro caso que vamos observar para entender por que o tempo de execução do caso médio do quick sort é O(nlog2n) é o que aconteceria se em metade do tempo em que não recebemos uma divisão 3-para-1, recebêssemos a divisão do pior caso. Vamos supor que a divisão 3-para-1 e o pior caso se alternem, e vamos pensar em um nó na árvore com k elementos no seu subarray. Então, veríamos uma parte da árvore que seria assim:
em vez de com esta aparência:
Portanto, mesmo se pegássemos a divisão no pior caso na metade do tempo e uma divisão 3-para-1 ou melhor na outra metade, o tempo seria aproximadamente duas vezes o tempo de execução do caso em que pegamos apenas divisões de 3-para-1. Novamente, esse é só um fator constante, e ele é absorvido dentro da notação O e, portanto, neste caso em que alternamos entre o pior caso e a divisão 3-para-1, o tempo é O(nlog2n).
Lembre-se de que essa análise não é matematicamente rigorosa, mas nos dá uma ideia intuitiva de por que o tempo de execução médio seria O(nlog2n).

Ordenação rápida aleatória

Suponha que o seu pior inimigo tenha te dado um arranjo para ordenar usando a ordenação rápida, sabendo que você sempre escolhe o elemento mais a direita como pivô, e organizou o arranjo de forma que você sempre pegue a divisão do pior caso. Como você pode frustrar o seu inimigo?
Você poderia não necessariamente escolher o elemento mais a direita de cada arranjo como pivô. Ao invés, você poderia aleatoriamente escolher um elemento no subarranjo, e usar esse elemto como o pivô. Mas espere—a função partitição assume que o pivô está na posição mais a direita do subarranjo. Sem problemas—apenas substitua o elemento que você escolheu pelo elemento mais a direita, e então particione como anteriormente. Apenas se o seu inimigo saiba como como você escolheu aleatoriamente as localizações no subarranjo, você ganhou!
De fato, com um pouco mais de esforço, você pode melhorar sua chance de conseguir uma divisão que está na pior dos 3-para-1. Aleatoriamente escolha não um, mas três elementos do subarranjo, e calcule a média dos três valores como sendo o pivô (substituindo este pelo elemento mais a direita). Por média, queremos dizer o elemento que está no meio dos três valores. Nós não mostraremos o por que, mas se você escolher a média dos três valores aleatoriamente como pivô, você tem 68,75% de chance (11/16) ode conseguir a divisão 3-para-1 ou melhor. Você pode ir ainda mais além. Se você escolher cinco elementos aleatoriamente e calcular a média como sendo o pivô, sua chance de conseguir uma divisão 3-para-1 aumenta para 79,3% (203/256). Se você calcular a média para sete elementos aleatórios, o valor vai para 85,9% (1759/2048). A mediana de nove elementos? Cerca de 90,2% (59123/65536). A mediana de 11? Cerca de 93,1% (488.293/524.288). Você entendeu. Claro, isso não necessariamente significa para pegar um número grande de elementos aleatoriamente e calcular a média, o tempo que você gastaria fazendo isso teria um efeito oposto ao tempo necessário para conseguir boas divisões quase o tempo todo.
Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.

Quer participar da conversa?

Nenhuma postagem por enquanto.
Você entende inglês? Clique aqui para ver mais debates na versão em inglês do site da Khan Academy.