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