Mesclar complexidade do tempo de classificação

A complexidade do tempo é o tempo de execução relativo de um programa. Pode ser visto como o número das principais operações de um programa.

Divisão inteira por dois

A divisão inteira é necessária ao fazer um tipo de mesclagem.

Quando um número ímpar é dividido por dois, há um restante de 1. Por exemplo:

7/2 = 3 r 1

Divisão Inteiro significa levar o número inteiro como sua resposta e abandonar o 1.

Quando um número par é dividido por dois, há um restante de 0. Por exemplo:

6 /2 = 3 r 0

Divisão inteira significa tomar o número inteiro como sua resposta e abandonar o 0.

Em ambos os casos, todo o número é levado e o restante é abandonado.

O objetivo deste artigo é determinar a complexidade do tempo do tipo de mesclagem, escrita também como mesclagem. Classificar pode estar ascendente ou descendente. Classificar neste artigo refere -se a classificar ascendente.

Algoritmo de classificação de mesclagem

Merge Sort é um algoritmo de classificação de divisão e conquista. Neste algoritmo, a lista não classificada é dividida em duas metades usando a divisão inteira. Cada uma das metades é dividida em duas metades novamente usando a divisão inteira. Esta divisão continua até que a lista seja considerada como elementos únicos separados.

A partir da esquerda, os elementos consecutivos são então emparelhados de maneira classificada. Os elementos emparelhados são então emparelhados novamente em uma forma classificada. Este agrupamento por pares continua até que toda a lista seja reformada e classificada.

Complexidade do tempo linear e logarítmico

Considere o seguinte código no idioma C:

para (int i = 0; i<8; i++)
int k = i + 1;
printf ("%d", k);

printf ("\ n");

A saída é:

1 2 3 4 5 6 7 8

O código é um loop for (ignorando a declaração de impressão logo após o loop for para o loop). Imprime os números inteiros de 1 a 8, para um total de 8 números. O conteúdo do corpo do loop for:

int k = i + 1;
printf ("%d", k);

Essas duas declarações são consideradas uma operação principal nesta situação. Existem 8 operações. Seja n 8. Esta é uma complexidade do tempo linear e está escrito da seguinte maneira:

Sobre)

Onde n é o possível número máximo de operações. Esta é a notação grande. Começa com O na mancha e seguido de parênteses. Dentro dos parênteses está o número máximo possível de operações.

Considere agora o seguinte código em que dos 8 números, 3 números são impressos:

para (int i = 0; i<8; i++)
int k = i + 1;
printf ("%d", k);
if (k == 3) quebra;

printf ("\ n");

A saída é:

1 2 3

O código é um loop for (ignorando a declaração de impressão logo após o loop for para o loop). Ele imprime os números inteiros de 1 a 3 de 8 números. O conteúdo do corpo do loop for:

int k = i + 1;
printf ("%d", k);
if (k == 3) quebra;

Ainda assim, essas três declarações são consideradas uma operação principal nesta situação. Existem 3 operações em 8.

Agora,

8 = 2³
=> 3 = log₂(8)

Portanto, o número de operações principais realizadas pelo código anterior é 3 (de 8).

Seja n 8. Esta é uma complexidade do tempo logarítmico e está escrito como:

O (log₂n)

Onde (log₂ n) significa 3 para o código anterior.

Havia 8 números. Em geral, quando o número de operações para o código está entre 2 e 5 em 8 e não apenas 3, a complexidade do tempo é descrita como log₂(n).

Exemplo de lista não classificada e classificada

Um exemplo de lista não classificada é a seguinte:

P V d q s x t b

Existem oito elementos na lista. Quando esta lista é classificada, torna -se:

B D P Q S T V X

Contando o número de operações principais no tipo de mesclagem

A seguinte lista:

P V d q s x t b

é usado para contar o número de operações principais no tipo de mesclagem.

A divisão inteira por dois fornece o seguinte resultado:

P V d q s x t b

Esta é uma operação. Outra divisão de ambas as partes por duas dá o seguinte resultado:

P V d q s x t b

Estas são três operações até agora (um mais dois). Outra divisão de cada nova parte por duas dá o seguinte resultado:

P V d q s x t b

Estas são sete operações até agora (três mais quatro). A lista dos oito elementos agora é considerada oito elementos separados, com um total de sete operações até agora. A próxima fase é emparelhar durante a classificação, começando da esquerda. Então, o próximo resultado é:

P V d q s x b t

Existem duas mudanças na posição para o último par. Duas mudanças são duas operações. Isso faz um total de nove operações até agora (sete mais dois).

O emparelhamento e a classificação continuam, sempre começando da esquerda para dar o seguinte resultado:

D p q v b s t x

Cada um desses dois grupos teve quatro mudanças na posição, fazendo oito operações. Existem dezessete operações até agora (nove mais oito). O emparelhamento e a classificação continuam e, finalmente, para dar o seguinte resultado:

B D P Q S T V X

Há sete mudanças na posição aqui, fazendo sete operações. Isso faz de vinte e quatro operações (dezessete mais sete) para a classificação completa.

Complexidade do tempo para classificação de mesclagem

A contagem anterior (ilustração) é usada para citar a complexidade do tempo para o Mergesort. Existem vinte e quatro operações.

24 = 8 x 3

Aquilo é:

24 = 8 x log₂(8)

porque o log2 (8) é 3.

Seja 8. Com isso, a complexidade do tempo de mesclagem é dada por:

Sobre.registro₂n)

onde o ponto significa multiplicação.

Na prática, de 8 elementos, o número de operações é de aproximadamente 24 ou 24.

Conclusão

O Mergesort é um algoritmo de classificação de divisão e conquista em particular. É um algoritmo de classificação muito eficiente. Sua complexidade de tempo é muito satisfatória, em comparação com os outros algoritmos de classificação. Sua complexidade de tempo é:

O (nlog₂n)

Nota: O número de operações não deve necessariamente ser exatamente n.log2n . No entanto, deve se aproximar.

A fusão de codificação precisa de funções recursivas. Não é muito difícil codificá -lo depois que o algoritmo for entendido. Codificar o tipo de mesclagem é uma discussão para outra hora.