Antes de ler este artigo é necessário que você já tenha lido o artigo sobre comportamento assintótico. Se você ainda não leu, clique aqui.
Vimos no último artigo a importância da identificação do comportamento assintótico para o processo de análise de algoritmos. Neste artigo vamos conhecer as classes assintóticas. Classes que a ciência da computação utiliza para classificar os algoritmos de acordo com o seu desempenho.
Introdução às classes assintóticas de algoritmos
Foi mostrado que a função de complexidade T(n) de um algoritmo fornece poucos detalhes a respeito da sua eficiência. Entretanto, a análise gráfica do seu comportamento assintótico consegue mostrar com maior precisão como se comporta o seu desempenho durante a sua execução.
O segredo do comportamento assintótico de um algoritmo está no termo polinomial de maior grau da sua função de complexidade, pois esse termo define a sua classe assintótica. Veja abaixo:
Veja abaixo uma lista com as classes assintóticas mais comuns existentes em análise de algoritmos.
Um pouco menos eficientes que os lineares. Essa é uma classe assintótica típica dos algoritmos que implementam o paradigma de “divisão e conquista”.
Na verdade, esta é uma situação muito improvável, pois ocorre em algoritmos que não realizam nenhuma computação significativa e, portanto, não possuem muita utilidade.
Diferença de eficiência em uma mesma classe
E se dois algoritmos forem da mesma classe assintótica? Qual será o mais eficiente?
Dois algoritmos pertencentes a uma mesma classe possuem o mesmo comportamento assintótico. Isso significa que: as pequenas variações de desempenho entre algoritmos de uma mesma classe não possuem grande importância.
Vejamos o porquê:
Imagine dois algoritmos C e D, ambos de classe linear:
Algoritmo C
Algoritmo D
Abaixo, segue a tabela com a quantidade de instruções realizadas pelos algoritmos para os valores iniciais de n. Percebe-se que o algoritmo C é mais eficiente que o D, apesar de ambos serem da mesma classe assintótica (a classe linear).
Independente do fato do algoritmo C ser mais eficiente do que o D, essa diferença entre as eficiências nunca se propagará. Observe nos gráficos ilustrados abaixo como a diferença de eficiência entre ambos sempre permanecerá constante para valores diferentes de n.
Perceba que, independente de quão grande for o valor de n, a diferença de eficiência entre os algoritmos de uma mesma classe assintótica sempre permanecerá constante. Por este motivo, as constantes aditivas e multiplicativas da fórmula de complexidade não são importantes para a análise. Em algoritmos pertencentes a uma mesma classe, o desempenho será muito parecido para grandes valores de n(n→∞).
Desta forma, fica claro que, para a análise de algoritmos, o que importa é apenas definir a classe do algoritmo, pois ela define o seu comportamento assintótico.
Diferença de eficiência em classes distintas
Em algoritmos de classes assintóticas distintas, a diferença de eficiência se propagará ao passo que o valor de n cresce. Considere os dois algoritmos E(classe quadrática) e F(classe linear):
Algoritmo E
Algoritmo F
Abaixo, segue a tabela com a quantidade de instruções realizadas pelos algoritmos para os valores iniciais de n. Percebe-se que o algoritmo F é mais eficiente que o E.
O interessante de ser observado aqui é que essa diferença de eficiência entre os algoritmos se propaga ao passo que o valor de n cresce, pois trata-se de dois algoritmos de classes assintóticas distintas. Observe nos gráficos ilustrados abaixo como a diferença de eficiência entre ambos se propaga para valores diferentes de n.
Perceba que, ao passo que o valor de n cresce, a diferença de eficiência entre os algoritmos fica cada vez mais acentuada. Portanto, fica clara a importância das classes assintóticas para o processo de análise. Em algoritmos pertencentes à classes distintas, o desempenho sofrerá muito impacto para grandes valores de n(n→∞).
Continue os seus estudos neste curso e leia o próximo artigo onde introduzimos o conceito de notação assintótica (a famosa notação BIG O), usada para representar formalmente os comportamentos assintóticos em análise de algoritmos.
