fbpx

Comportamento assintótico (análise de algoritmos)

Aprofunde os seus conhecimentos em análise de algoritmos. Conheça a importância do comportamento assintótico das funções geradas pelo processo de análise.

compartilhe este artigo

Compartilhar no facebook
Compartilhar no twitter
Compartilhar no linkedin
Compartilhar no email

compartilhe este artigo

Compartilhar no facebook
Compartilhar no twitter
Compartilhar no linkedin
Compartilhar no whatsapp
Compartilhar no email

Introdução ao comportamento assintótico

De uma maneira simplificada e mais objetiva possível, o comportamento assintótico pode ser entendido como a curva de crescimento da função gerada pelo processo de análise de algoritmos. 

Sabe-se que o objetivo da análise de algoritmos é encontrar uma fórmula fechada que represente a quantidade de instruções executadas pelo algoritmo em função da sua entrada n. Por exemplo: o algoritmo de ordenação Bubble Sort (no pior caso) possui complexidade T(n)=5n2-n+1. Isso significa que se a sua entrada n for igual a 4 (um arranjo de tamanho 4), a quantidade de instruções executadas pelo algoritmo para ordenar esse arranjo será igual a:

Se você ainda não sabe como se faz o processo de análise em algoritmos, clique neste link e acesse o artigo onde te ensinamos o passo a passo para encontrar a fórmula de complexidade.

As fórmulas encontradas pelo processo de análise são de grande importância para mensurar a eficiência dos algoritmos. No entanto, a ciência da computação faz uso de uma metodologia mais formal para separar os algoritmos em classes específicas de desempenho. Essa separação é realizada com base em uma métrica denominada de comportamento assintótico.

Para entender o conceito de comportamento assintótico, precisamos analisar a função em um gráfico e observar como a quantidade de instruções cresce em função do valor da entrada n. Para tanto, vamos analisar três algoritmos abordados no artigo anterior (onde falamos sobre o processo de análise) e vamos comparar as suas fórmulas de complexidade para perceber algumas coisas bem interessantes. São eles:

  • Algoritmo que lê uma idade informada pelo usuário. Complexidade: T(n)=7
  • Algoritmo que imprime todos os números de um arranjo. Complexidade: T(n)=3n+2
  • Algoritmo de ordenação Bubble Sort. Complexidade: T(n)=5n2-n+1

Análise da curva de crescimento das funções

Para cada um dos algoritmos, criaremos um gráfico: (valor de n) vs (nº de instruções executadas).

Comportamento assintótico do algoritmo que lê uma idade: T(n)=7

Este é um algoritmo de complexidade constante. Se olharmos o gráfico da função ilustrado abaixo, percebemos a constância do seu comportamento. A quantidade de instruções executadas (eixo vertical) não cresce em função dos valores de n (eixo horizontal). O número de instruções sempre permanece igual a 7.

comportamento-assintótico-01

Comportamento assintótico do algoritmo que imprime um arranjo: T(n)=3n+2

Este é um algoritmo de complexidade linear. Se olharmos o gráfico da função ilustrado abaixo, percebemos que o número de instruções executadas pelo algoritmo (eixo vertical) cresce de maneira linear, em relação aos valores de n (eixo horizontal).

comportamento-assintótico-02

Comportamento assintótico do algoritmo Bubble Sort: T(n)=5n2-n+1

O algoritmo Bubble Sort possui complexidade quadrática (no pior caso). Se olharmos o gráfico da função ilustrado abaixo, percebemos que o número de instruções executadas pelo algoritmo (eixo vertical) cresce de maneira quadrática em relação aos valores de n (eixo horizontal).

comportamento-assintótico-03

Comparação entre os algoritmos

Quando sobrepomos os gráficos das funções de complexidade dos três algoritmos (imagem abaixo), podemos perceber a tendência de crescimento de cada uma das funções. Observe como a função quadrática (linha vermelha) tende a apresentar uma quantidade de instruções cada vez maior para cada novo tamanho n do problema! Isso significa que o algoritmo quadrático é menos eficiente que os outros dois, os quais possuem uma tendência de crescimento menor.

comportamento-assintótico-04

Portanto, o que realmente importa em uma função T(n) de um algoritmo é entender o seu padrão de crescimento ao passo que o valor de n cresce. A esse “padrão de crescimento” damos o nome de comportamento assintótico. Esse é o aspecto chave para a análise de algoritmos.

Um comportamento assintótico equivocado

Vamos a um exemplo bem ilustrativo para mostrar a importância do comportamento assintótico dos algoritmos. Foi realizada uma análise em dois algoritmos (A e B) que resultou nas seguintes funções de complexidade:

Algoritmo A
Algoritmo B

Pergunta: Qual o algoritmo mais eficiente?

Observe abaixo uma tabela que mostra a quantidade de instruções executadas por cada um deles para os valores iniciais de n:

análise de algoritmos
análise de algoritmos

Aparentemente (olhando a tabela) somos tentados a dizer que o algoritmo A é mais eficiente por apresentar quantidade de instruções bem menores para os mesmos valores de n. Mas observe o que acontece quando analisamos a quantidade de instruções para valores maiores de n:

análise de algoritmos
análise de algoritmos

Observe que até o valor de n=209 o algoritmo A é mais eficiente que o B, mas a partir do valor de n=210 o quadro se inverte e o algoritmo B passa a ser mais eficiente que o A.

As constantes multiplicativa e aditiva, respectivamente 100 e 1000, na função do algoritmo B dão a falsa impressão de que ele é menos eficiente, mas elas só adiam o inevitável.

Veja abaixo o gráfico plotado para ambas as funções. Perceba como, a partir do valor de n=210, a quantidade de instruções executadas pelo algoritmo B é superada pela do algoritmo A:

comportamento-assintótico-05

O que acabamos de fazer neste exemplo foi analisar o comportamento assintótico dos dois algoritmos. Analisamos a tendência de crescimento das instruções dos algoritmos quando n possui um valor muito grande, quando n tende ao infinito (n → ∞).

O fato do algoritmo A ser quadrático, já nos dá a pista de que, para valores muito grandes de n (n → ∞), a sua quantidade de instruções irá superar o a quantidade de instruções do algoritmo B, que é linear. Por este motivo, todas as constantes aditivas e multiplicativas da função de complexidade de um algoritmo não exercem nenhum impacto no seu comportamento.

Desta forma, entende-se que: nem o denominador 2 (do algoritmo A) e nem o fator 100 e a parcela 1000 (do algoritmo B) podem impedir que o algoritmo B seja mais eficiente que o A para grandes valores de n.

Para se aprofundar ainda mais em análise de algoritmos e aprender sobre as classes assintóticas, clique aqui e acesse o artigo onde te explicamos detalhadamente sobre o assunto.

compartilhe este artigo

Compartilhar no facebook
Compartilhar no twitter
Compartilhar no linkedin
Compartilhar no email
Compartilhar no facebook
Compartilhar no twitter
Compartilhar no linkedin
Compartilhar no whatsapp
Compartilhar no email

Sobre o autor

Almir Santiago

Almir Santiago

MSc in Systems and Computing, Professor of Computer Programming, Algorithms and Data Structures.

Deixe um comentário