Melhor resposta
Como você tem conhecimento suficiente de como a classificação rápida funciona, como encontrar o pivô, dividir a matriz atual e fazer novamente o mesmo recursivamente para cada submatriz, é fácil analisar a complexidade do tempo levando esses itens em consideração:
Pior caso:
O pior caso ocorre quando, a cada recursão, obtemos o próximo pivô para dividir matrizes no final da matriz.
Se N é o comprimento da matriz e tendo o pivô atual na posição inicial da matriz,
o pivô no último índice é identificado apenas percorrendo a matriz do início ao fim. Depois de fixar o pivô e dividir as submatrizes resultantes de comprimento são (N-1), 1 .
Novamente isto (N-1) a submatriz encontra o próximo pivô nas partições da matriz resultante do índice com comprimentos (N-2), 1 .
Esse processo se repete até que os comprimentos finais das submatrizes sejam 1,1 .
Então, isso pode ser matematicamente desenhado no papel como
na etapa 1: com N elementos, a complexidade de tempo para esta partição é
T (N) = N + T (N-1)
Onde T (N-1) é a complexidade de tempo da partição para ser processado recursivamente e N é o tempo necessário para comparar N elementos com um pivô fixo.
na etapa 2: com N-1 elementos ,
T (N-1) = (N-1) + T (N-2)
T (N-2) = (N-2) + T (N-3)
…
T (3) = 3 + T (2)
T (2) = 2 + T (1)
T ( 1) = 0, pois o tempo para particionar a matriz com comprimento 1 é 0 sem partições
Portanto,
T (N) = N + (N-1) + (N-2) … + 3 + 2 ≈ N * (N + 1) / 2
= (N ^ 2) / 2
= O (N ^ 2)
Caso médio :
No caso médio, o próximo pivô divide a matriz em dois comprimentos iguais (N / 2) comparando todos os elementos que resultam em complexidade de tempo N.
T (N) = 2 * T (N / 2) + N
divide ambos os lados por N
T (N) / N = 2 * (T (N / 2) / N) + N / N
T (N) / N = 2 * (T (N / 2) / N) + 1
Portanto, T (N) / N = (T (N / 2) / (N / 2)) + 1
T (N / 2) / (N / 2) = T (N / 4) / (N / 4) + 1
…
T (2) / 2 = T (1) / 1 + 1
Como T (1) = 0
T (2) / 2 = 1
T (4) / 4 = T (2) + T (1)
T (8) / 8 = T (4) + T (2) + T (1) ## log (n) termos
Portanto, T (N) / N = log N
T (N) = NlogN
Resposta
QuickSort é um algoritmo de divisão e conquista. Ele escolhe um elemento como pivô e particiona o array fornecido ao redor do pivô escolhido. Existem muitas versões diferentes do quickSort que selecionam o pivô de maneiras diferentes.
- Sempre selecione o primeiro elemento como um pivô.
- Sempre escolha o último elemento como o pivô (implementado abaixo)
- Escolha um elemento aleatório como pivô.
- Escolha a mediana como um pivô.
O processo-chave no quickSort é uma partição ( ) O alvo das partições é, dado uma matriz e um elemento x da matriz como um pivô, colocar x em sua posição correta em uma matriz classificada e colocar todos os elementos menores (menores que x) antes de x, e colocar todos os elementos maiores (maiores do que x) após x. Tudo isso deve ser feito em tempo linear.
As etapas da classificação rápida são:
Step 1 − Choose the highest index value has a pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − left points to the low index
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at the right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is the new pivot
Implementação do quicksort:
Quicksort(A,p,r) {
if (p
q
Quicksort(A,p,q)
Quicksort(A,q+1,r)
}
}
Partition(A,p,r)
x
i
j
while (True) {
repeat
j
until (A[j]
i
until (A[i] >= x)
if (i A[j]
else
return(j)
}
}
Complexidade de tempo do quicksort:
Pior Caso: o pior caso ocorre quando o processo de partição sempre escolhe o maior ou o menor elemento como pivô. Se considerarmos a estratégia de partição acima, onde o último elemento é sempre escolhido como um pivô, o pior caso ocorreria quando a matriz já estivesse classificada em ordem crescente ou decrescente. A seguir está a recorrência para o pior caso.
T(n) = T(0) + T(n-1) + (n)
which is equivalent to
T(n) = T(n-1) + (n)
A complexidade da recorrência acima é n quadrados
Melhor caso: O melhor caso ocorre quando o processo de partição sempre escolhe o elemento do meio como pivô. A seguir está uma recorrência para o melhor caso.
T(n) = 2T(n/2) + (n)
A complexidade da recorrência acima é nLogn
Caso médio: Para fazer a análise de caso médio, precisamos considerar todas as permutações possíveis do array e calcular o tempo gasto por cada permutação que não parece fácil. Podemos ter uma ideia do caso médio considerando o caso em que a partição coloca O (n / 9) elementos em um conjunto e O (9n / 10) elementos em outros conjuntos. A seguir está uma recorrência para este caso.
T(n) = T(n/9) + T(9n/10) + (n)
A complexidade da recorrência acima é nLogn
Complexidade espacial do quicksort :
O espaço usado pelo quicksort depende da versão usada.
A versão no local do quicksort tem uma complexidade de espaço de O (log n), mesmo em o pior caso, quando é cuidadosamente implementado usando as seguintes estratégias:
- particionamento in-loco é usado. Esta partição instável requer espaço O (1).
- Após o particionamento, a partição com menos elementos é (recursivamente) classificada primeiro, requerendo no máximo espaço O (log n). Em seguida, a outra partição é classificada usando recursão ou iteração de cauda, que não adiciona à pilha de chamadas. Essa ideia, conforme discutido acima, foi descrita por R. Sedgewick e mantém a profundidade da pilha limitada por O (log n).