Contando complexidade de classificação

O que está contando o tipo?

Contar o tipo é melhor ilustrado com a classificação de números inteiros. Em C/C ++ e Java, os personagens são inteiros e podem ser classificados da maneira como os números inteiros são classificados. Considere a seguinte lista não classificada de números inteiros:

16, 20, 12, 10, 18, 8, 12, 18, 12, 14, 14

Esta lista é classificada em ordem crescente. Pode ser dado (recebido pelo programa de classificação) como uma matriz. Consiste em números positivos maiores ou iguais a 0.

Observe aqui que o número inteiro mais alto é 20. Então, 20 + 1 = 21, novos locais de matriz devem ser fornecidos. O extra 1 é para a possibilidade de que um dos números inteiros seja classificado é 0. Lembre -se de que o programa de classificação não sabe os números a serem classificados com antecedência. Então, a possibilidade de ter 0 deve ser feita.

Para cada índice da nova matriz que corresponde a um valor na lista especificada, o número de ocorrência do valor na lista especificada é atribuída como o valor para essa nova célula de matriz. Isto é, a nova matriz consiste em contadores. A lista não classificada anterior é representada da seguinte maneira:

0	0	0	0	0	0	0	0	1	0	1	0	3	0	1	0	1	0	2	0	1
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20

Esta tabela representa uma matriz que é a nova variedade de contadores. Nesta fase, existem duas matrizes: a matriz fornecida da lista não classificada e a variedade de contadores chamados de contagem Array.

Na tabela, a segunda linha tem os índices. A primeira linha tem as contagens. Cada contagem é o número de ocorrência do índice correspondente encontrado como o valor na lista não classificada.

Para os índices 0 a 7 (inclusive), a contagem é 0. Isso ocorre porque nenhum desses índices é um valor na lista não classificada. O índice 8 ocorre uma vez na lista, então sua contagem é 1. O índice 9 ocorre zero vezes na lista, então sua contagem é 0. O índice 10 ocorre uma vez na lista, então sua contagem é 1. O índice 12 ocorre três vezes na lista, então sua contagem é 3. O índice 13 ocorre zero vezes na lista, então sua contagem é 0. Isso continua até o índice 20 com uma contagem de 1 enquanto o índice 18 tem uma contagem de 2.

A lista classificada é a seguinte:

8, 10, 12, 12, 12, 14, 16, 18, 18, 20

Isso pode ser obtido da matriz Count (nova) da seguinte maneira:

Movendo -se da esquerda para a direita, se o valor de um índice for 0, esse valor não estará na lista não classificada (matriz) dada (matriz). Se o valor for 1, digite o índice uma vez. Se o valor for 2, digite o índice duas vezes. Se o valor for 3, digite o índice três vezes. Se o valor for 4, digite o índice 4 vezes e assim por diante. Tudo isso pode ser feito de volta na matriz não classificada (lista).

Contando o algoritmo de classificação

• Forneça uma matriz cujo comprimento é o número máximo na lista não classificada, mais 1 (para explicar um possível 0 na lista). O índice desta matriz é um valor possível na lista não classificada.
• Leia a matriz de contagem da esquerda para a direita e digite o índice cujo valor não é 0 e o número de vezes para o valor da célula do índice.

Operações

O algoritmo tem dois passos. Para a lista de dados anteriores, o primeiro passo tem 10 operações principais porque o número de elementos na lista não classificada é 10. A segunda etapa tem 21 operações principais porque o valor máximo na lista não classificada é 20 (o ser extra 1 é para um possível valor 0). Portanto, o número de operações principais é considerado o seguinte:

O (10 + 20)

Onde 10 é o número de elementos na lista não classificada e 20 é o valor máximo na lista não classificada. O adicionado 1 a 20 é ignorado neste momento, mas lembre -se de que deve ser codificado.

Complexidade do tempo para contar a classificação

A complexidade do tempo é o número aproximado das operações principais para algum código. A complexidade do tempo indica a velocidade do código. A complexidade do tempo para contagem de classificação é dada da seguinte maneira:

O (n + m)

Onde n é o número de elementos (comprimento ou tamanho) da matriz não classificada dada, e M é o valor máximo na matriz não classificada dada. O adicionado 1 a M é ignorado neste momento. O Big-O com seus parênteses e conteúdo é referido como a notação Big-O.

Observe que, para obter o valor máximo na matriz, algumas operações devem ocorrer no código. No entanto, essas operações são ignoradas ao citar a complexidade do tempo.

A matriz de contagem deve ter todos os seus elementos inicialmente feitos como zero. Todas essas operações também são ignoradas ao citar a complexidade do tempo para o tipo de contagem.

Espaço de memória

Observe que, na matriz de contagem anterior, todas as contagens de 0 são redundantes. Embora seus espaços sejam redundantes na memória, eles precisam estar lá. O tipo de contagem ocupa espaço de memória desnecessário em geral. Normalmente, nada é feito para evitar os locais redundantes. Se o valor mínimo na matriz não classificada pode ser conhecida, a parte inicial da matriz de contagem poderá ser omitida para reduzir o espaço. No entanto, os zeros intercalados na matriz de contagem não podem ser omitidos.

Nota: Há também complexidade espacial, mas isso não é abordado neste artigo.

Codificação em c

Uma função de classificação de contagem na linguagem C do computador é a seguinte:

Void CountingSort (int arr [], int n)
int max = 0;
para (int i = 0; i max)
max = arr [i];


int contagem [max+1];
para (int i = 0; i< max+1; i++)
contagem [i] = 0;

// n
para (int i = 0; i< n; i++)
contagem [arr [i]] = contagem [arr [i]] + 1; // Adicione 1 para cada ocorrência

// m
int k = 0; // índice para determinada matriz
para (int i = 0; ise (conde [i] != 0)
for (int j = 0; jarr [k] = i; // colocando o valor classificado de volta em determinada matriz
k ++;

O loop e a entrada aninhados são os seguintes:

16, 20, 12, 10, 18, 8, 12, 18, 12, 14, 14

Na verdade, existem 24 operações principais e não 20. A operação extra 3 + 1 = 4 é ignorada ao citar a complexidade do tempo para o tipo de contagem.

Uma função principal C adequada é a seguinte:

int main (int argc, char ** argv)

int n = 10;
int arr [] = 16, 20, 12, 10, 18, 8, 12, 18, 12, 14;
contingsort (arr, n);
para (int i = 0; iprintf ("%d", arr [i]);
printf ("\ n");
retornar 0;

A saída é:

8 10 12 12 12 14 16 18 18 20

Conclusão

A complexidade do tempo para o tipo de contagem é:

O (n + m)

Onde m é geralmente maior que n, n é o número de elementos (comprimento) da lista não classificada e m é o elemento máximo na lista não classificada dada.