A complexidade do tempo do Quicksort, expressa em grande notação O, varia dependendo dos dados de entrada:
*
Melhor caso: O (n log n)
*
Caso médio: O (n log n)
*
Pior caso: O (n^2)
Aqui está um colapso:
*
Melhor caso e caso médio (O (n log n)): Isso ocorre quando o elemento pivô escolhido em cada etapa divide a matriz em metades aproximadamente iguais. Nesse cenário, o algoritmo faz com que as chamadas recursivas de log n (porque está efetivamente reduzindo a metade do tamanho do problema) e cada nível de recursão requer o trabalho O (n) para particionar a matriz. Portanto, a complexidade total do tempo é O (n log n).
*
pior caso (o (n^2)): Isso acontece quando o elemento dinâmico é repetidamente o menor ou o maior elemento da matriz. Isso leva a partições muito irregulares. Em essência, em vez de dividir a matriz pela metade, você está apenas reduzindo o tamanho do problema em um elemento a cada vez. Isso resulta em N chamadas recursivas, e cada chamada ainda leva o tempo para a partição (porque você está comparando quase todos os elementos). Consequentemente, a complexidade total do tempo se degrada para O (n^2).
Mitigação do pior cenário: O pior cenário pode ser mitigado por:
*
Seleção de pivô randomizada: A escolha do pivô ajuda a evitar consistentemente escolher o menor ou o maior elemento, tornando o caso O (n^2) muito menos provável.
*
Mediana de três seleção de pivô: Selecionar a mediana dos primeiros, meio e último elementos da matriz, pois o pivô também pode ajudar a evitar opções de pivô consistentemente ruins.
Na prática, o Quicksort geralmente é muito eficiente devido ao seu bom desempenho de casos médios e ao fato de tender a ter fatores constantes mais baixos do que outros algoritmos de classificação de O (n log n), como o tipo de mesclagem. No entanto, é importante estar ciente do potencial para o comportamento do pior caso O (n^2).
