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.

Nos siga em nossas redes sociais.

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

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.

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:

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:

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:

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.

Nos siga
em nossas redes sociais.

Nos siga em nossas redes sociais.