Complexidade de tempo de classificação rápida
Agora, existem diferentes maneiras de escrever as funções Pivot () e Partition (). A escolha do tipo de função pivot () e/ou partition () determina a eficiência de todo o programa. A eficiência é como o número de operações principais que são realizadas pelo programa.
A complexidade do tempo é o tempo de execução relativo de um programa. Isso pode ser visto como a operação principal do programa.
Classificar pode estar ascendente ou descendente. Neste artigo, a classificação está ascendendo.
O objetivo deste artigo é produzir a complexidade do tempo para um programa Quicksort. Como o Quicksort pode ser escrito de maneiras diferentes, dependendo da escolha das funções pivot () e/ou partition (), cada tipo de rastreamento rápido tem sua própria complexidade de tempo. No entanto, há uma série de várias operações nas quais os diferentes tipos de programas Quicksort se encaixam. Este artigo apresenta apenas um dos diferentes tipos de programas da Quicksort. Qualquer segmento de código apresentado é da linguagem C.
Divisão inteira por dois
Quick Sort usa divisão inteira para dividir seu conjunto principal em conjuntos menores.
Agora,
11/2 = 5 restante 1
Divisão Inteiro significa, pegando 5 e abandonando 1. Isto é, aceite o número inteiro e ignore o restante.
Também,
10/2 = 5 restante 0
Aqui, o restante é zero e não importa. Ainda assim, a divisão inteira pega 5 e abandona 0. Isto é, aceite o número inteiro e ignore o restante que estiver lá, mesmo que seja zero. Às vezes na programação, também é bom saber se o restante é 0 ou não - veja mais tarde.
Ao dividir uma lista em divisão inteira e rápida, é o que é usado.
Para uma classificação rápida, para obter o índice intermediário baseado em zero para uma lista, faça a divisão inteira por dois pela duração da lista. Todo o número é o índice médio baseado em zero. Para obter a duração da lista, comece a contar de 1.
Complexidade do tempo relacionada à classificação rápida
Considere o seguinte código:
int n = 8;char a [] = 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h';
para (int i = 0; i
printf ("\ n");
A saída é:
a b c d e f g hIsto é, todos os oito elementos foram impressos.
Existem oito elementos identificados por n. O corpo do loop for um conteúdo.
printf ("%c", a [i]);Esta é uma operação principal. Então, oito operações principais ocorreram. A complexidade do tempo para este código é escrita como:
Sobre)
Onde n é o número de operações principais. Esta é a notação grande. Na notação, a primeira letra é o em maiúsculas. Então há parênteses. Dentro dos parênteses está o número de operações ou o máximo possível número de operações.
Agora considere o seguinte segmento de código:
para (int i = 0; i<8; i++)para (int i = 0; i
if (i == 2)
quebrar;
printf ("\ n");
A saída é:
a b cO corpo do loop for um conteúdo.
printf ("%c", a [i]);if (i == 2)
quebrar;
Esta ainda é considerada uma operação principal nesta situação. Três elementos foram impressos porque a operação principal foi executada três vezes.
Agora,
8 = 23
=> 3 = log2(8)
Se 8 é n, então 3 é,
registro2(n)
E a complexidade do tempo seria dada como:
O (log2n)
Ainda há outro segmento de código a considerar em relação à complexidade do tempo do Quicksort. Isso é
para (int i = 0; iprintf ("\ n");
printf ("\ n");
A saída é:
a b c d e f g ha b c d e f g h
a b c d e f g h
a b c d e f g h
a b c d e f g h
a b c d e f g h
a b c d e f g h
a b c d e f g h
O número de caracteres impressos é 64, de um número inicial de 8. Isso significa que a operação principal foi executada 64 vezes.
64 = 8 x 8 = 82
Se 8 for n, então isso seria n2. A complexidade do tempo para este código é:
Sobre2)
Algoritmo de classificação rápida neste artigo
Para este artigo, as etapas do algoritmo são:
- Procure a mediana (veja abaixo) entre o primeiro elemento, o elemento médio e o último elemento da lista.
- Posicionar a mediana no meio da lista.
- Envie todos os elementos à direita que são menores que a mediana, agora no meio, à esquerda da mediana, e envie todos os elementos à esquerda que são maiores que a mediana à direita da mediana. Isso é chamado de particionamento.
- Repita as três etapas acima em ordem, para cada sub-lista, até que a lista seja separada em elementos únicos.
- Quando a lista consiste em elementos únicos separados, a lista é classificada.
Mediana
Para obter a mediana dos três elementos,
TÁXIreorganize os três elementos em ordem, eu.e.
A b cO elemento do meio, B, é a mediana.
Ilustração de classificação rápida
A lista a ser classificada é:
P V d q s x t bExistem oito elementos. Quando a lista for classificada, seria:
B D P Q S T V XEntão, o problema é: classificar a lista:
P V d q s x t bUsando o Quicksort.
A mediana entre P, Q e B é procurada. É p. Esta busca pela mediana envolve três operações. Então, há um total de três operações até agora. Colocar a mediana no meio da lista fornece:
V d q p s x t bLembre -se: o índice para o elemento intermediário é o resultado da divisão inteira por dois. Existem quatro movimentos aqui, para p e q. Essas são quatro operações. Isso faz um total de sete operações até agora (três mais quatro). Agora, B será enviado para a esquerda e V e Q serão enviados para a direita, para ter:
D B P V q S x TObserve que P não está mais no meio verdadeiro. No entanto, houve três movimentos. Estas são três operações. Portanto, existem dez operações até agora (sete mais três). Cada uma das duas sub-listas deve ser dividida em três partes (a mediana é uma parte).
A mediana para D e B é D. A busca pela mediana é de três operações. Isso faz um total de treze operações até agora (dez mais três). Particionando esses elementos dá:
B dHavia dois movimentos aqui. Essas são duas operações. Isso faz um total de quinze operações até agora (treze mais dois). Em seguida, a mediana do conjunto v, q, s, x, t deve ser procurada, e o conjunto particionou.
A mediana para V, S e T é T. A pesquisa mediana é três operações. Até agora, houve dezoito oito (quinze mais três). Colocar t no meio dá:
V q t s xExistem três movimentos aqui. Estas são três operações. O número total de operações até agora é de vinte e um (dezoito mais três). Enviando elementos inferiores à direita de T para a esquerda e elementos mais altos à esquerda de T à direita, dá:
Q s t v xExistem dois movimentos aqui. Estas são duas operações. Até agora, há um total de vinte e três operações (vinte e um mais dois). Juntando todas as partições até agora dá:
B D P Q S T V XObserve que a lista já está classificada. No entanto, o algoritmo precisa rescindir. Q, s e v, x precisam ser atendidos. Não haverá movimento de personagens entre esses dois. No entanto, sua mediana será vista. A busca por duas medianas é de seis operações. Isso faz um total de vinte e nove operações para todo o programa (vinte e três mais seis). A lista final classificada é:
B D P Q S T V XObservação:
24 = 8 x 3
=> 24 = 8xlog28
29 é aproximadamente igual a 24.
Conclusão
Dependendo do tipo de função escolhida para Pivot () e do tipo de função escolhida para partição (), a complexidade do tempo para o programa Quicksort estará em algum lugar entre
Sobre.registro2n)
e
Sobre2)
inclusive. Observe que o ponto em O (n.registro2n) significa multiplicação.