Siga-nos

Inscreva-se

Siga-nos

Inscreva-se

Classes assintóticas

Conheça as principais classes assintóticas e o significado de desempenho que elas representam para os algoritmos.

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:

No algoritmo:
classes-assintoticas-formula-01
O que realmente importa é o termo de maior grau, o n2. Portanto, é um algoritmo de classe quadrática.
No algoritmo:
classes-assintoticas-formula-02
O que realmente importa é o termo de maior grau, o n. Portanto, é um algoritmo de classe linear.
No algoritmo:
classes-assintoticas-formula-03
O que realmente importa é o termo de maior grau, o n2. Portanto, é um algoritmo de classe quadrática.
No algoritmo:
classes-assintoticas-formula-04
O que realmente importa é o termo de maior grau, o n. Portanto, é um algoritmo de classe linear.
No algoritmo:
classes-assintoticas-formula-05
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.
classes-assintoticas-graph-01
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.
classes-assintoticas-graph-02
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.
classes-assintoticas-graph-03
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).
classes-assintoticas-graph-04
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”.

classes-assintoticas-graph-05
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.
classes-assintoticas-graph-06
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.
classes-assintoticas-graph-07
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.
classes-assintoticas-graph-08

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:

classes-assintoticas-algo-c

Algoritmo C

classes-assintoticas-algo-d

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

classes-assintoticas-algo-c-table
classes-assintoticas-algo-d-table

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.

classes-assintoticas-anim-01

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):

classes-assintoticas-algo-e

Algoritmo E

classes-assintoticas-algo-f

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.

classes-assintoticas-algo-e-table
classes-assintoticas-algo-f-table

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.

classes-assintoticas-anim-02

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.

Este artigo foi útil para você?

Então nos ajude a crescer e compartilhe-o com outras pessoas que se interessam por esse assunto!

WhatsApp
Facebook
Twitter
LinkedIn
Email

Outros artigos

Siga-nos

Inscreva-se

Este site usa cookies para garantir que você obtenha a melhor experiência.