Qual é a complexidade de tempo da classificação rápida?

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.

  1. Sempre selecione o primeiro elemento como um pivô.
  2. Sempre escolha o último elemento como o pivô (implementado abaixo)
  3. Escolha um elemento aleatório como pivô.
  4. 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).

Deixe uma resposta

O seu endereço de email não será publicado. Campos obrigatórios marcados com *