Classes assintóticas (análise de algoritmos)

Continue aprofundando seus conhecimentos em análise de algoritmos. Conheça as classes assintóticas e as diferenças de desempenho entre elas.

Introdução às classes assintóticas de algoritmos

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.

Se você ainda não sabe o que é o comportamento assintótico de um algoritmo, clique neste link e acesse o artigo onde te explicamos detalhadamente a respeito do assunto.

Entendemos que a fórmula de complexidade de um algoritmo nos dá poucos detalhes a respeito da sua eficiência. Contudo, a análise do seu comportamento assintótico mostra exatamente 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 fórmula de complexidade, pois esse termo define a sua classe assintótica. Veja abaixo:

No algoritmo:
O que realmente importa é o termo de maior grau, o n2. Portanto, é um algoritmo de classe quadrática.
No algoritmo:
O que realmente importa é o termo de maior grau, o n. Portanto, é um algoritmo de classe linear.
No algoritmo:
O que realmente importa é o termo de maior grau, o n2. Portanto, é um algoritmo de classe quadrática.
No algoritmo:
O que realmente importa é o termo de maior grau, o n. Portanto, é um algoritmo de classe linear.
No algoritmo:
O que realmente importa é o termo de maior grau, o n. Portanto, é um algoritmo de classe linear.

Veja abaixo uma lista com as classes assintóticas mais comuns existentes em análise de algoritmos.

n!
Fatorial
A pior classe existente. Geralmente ocorre em alguns algoritmos que usam a técnica de força bruta para resolver problemas.
2n
Exponencial
Mais eficiente que o fatorial, porém ainda muito longe de ser um algoritmo eficiente. Também ocorre em algoritmos que usam força bruta para resolver problemas.
nk
Polinomial
São mais eficientes que os exponenciais, porém só são adequados para resolver pequenos problemas. Quando o valor de n cresce muito, o algoritmo se torna bastante ineficiente.
n2
Quadrática
Polinomiais de ordem quadrática. Essa classe ocorre bastante em algoritmos que processam informações aos pares. Geralmente em loops aninhados (um loop dentro do outro).
n log n
Linear logarítmica

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”.

n
Linear
Algoritmo muito eficiente. A classe linear ocorre em algoritmos que precisam processar n elementos de entrada e fazer pequenas computações sobre esses elementos.
log n
Logarítmica
O melhor dos mundos para os algoritmos. Essa classe é típica de algoritmos que podem resolver os problemas transformando-os em problemas menores a cada etapa da resolução.
1
Constante
O nirvana dos algoritmos.
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ças de eficiência entre algoritmos de uma mesma classe

E se dois algoritmos forem da mesma classe assintótica? Qual será o mais eficiente?

Para a análise de algoritmos, o que importa é apenas definir a classe do algoritmo, pois ela define o seu comportamento assintótico.

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.

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→∞).

Diferenças de eficiência entre algoritmos de classes diferentes

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 (quadrático) e F (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→∞).

Para se aprofundar ainda mais em análise de algoritmos e aprender sobre as notações assintóticas, clique aqui e acesse o artigo onde te explicamos detalhadamente sobre a primeira delas. A notação Big O.

Compartilhe este artigo

Share on whatsapp
WhatsApp
Share on facebook
Facebook
Share on twitter
Twitter
Share on linkedin
LinkedIn
Share on email
Email

Nos siga
em nossas redes sociais.