Antes de ler este artigo é necessário que você já tenha lido o artigo sobre melhor caso e pior caso da análise de algoritmos. Se você ainda não leu, clique aqui e confira.
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 (função) T(n) que represente a quantidade de instruções executadas pelo algoritmo em função da sua entrada n.
Por exemplo: o algoritmo findMax() (no pior caso) possui complexidade T(n)=4n. Isso significa que se a sua entrada n for igual a 4 (um array de tamanho 4), a quantidade de instruções executadas pelo algoritmo será igual a:
- T(4) = 4*4 = 16 instruções.
Da mesma forma, se a entrada n for igual a 10 (um array de tamanho 10), a quantidade de instruções executadas pelo algoritmo será igual a:
- T(10) = 4*10 = 40 instruções.
As funções T(n) encontradas pelo processo de análise são de grande importância para mensurar a eficiência dos algoritmos. A ciência da computação usa essas funções T(n) para separar os algoritmos em classes específicas de desempenho. E ela faz isso analisando o seu “comportamento assintótico”.
Para começar a 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 na próxima seção as funções T(n) de três algoritmos hipotéticos. São eles:
- Algoritmo 1. Complexidade: T(n)=7
- Algoritmo 2. Complexidade: T(n)=3n+2
- Algoritmo 3. Complexidade: T(n)=5n2-n+1
Curva de crescimento das funções
Para cada um dos algoritmos, criaremos um gráfico: (tam. da entrada n) x (qtd. de instruções executadas).
Comportamento assintótico do algoritmo 1: 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.
Pode-se observar no gráfico acima que 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 2: 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 3: T(n)=5n²-n+1
O algoritmo 3 possui complexidade quadrática. 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 tende a apresentar uma quantidade de instruções cada vez maior para cada novo tamanho n da entrada! Isso significa que o algoritmo quadrático é menos eficiente que os outros dois, os quais possuem uma tendência de crescimento menor.
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 quantidades de instruções bem menores para os mesmos valores de n.
Mas observe abaixo 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 a quantidade de instruções do algoritmo B, que por sua vez é 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 assintótico (a sua tendência de crescimento no gráfico).
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.
Exercício
Para que você possa praticar o conceito de comportamento assintótico de funções, tente resolver o exercício proposto.
- Algoritmo A: T(n) = n(n+5)
- Algoritmo B: T(n) = 10n+10
Analise graficamente as funções T(n) de complexidade de tempo dos algoritmos A e B acima e determine:
- Qual é o algoritmo “mais eficiente” e o “menos eficiente”?
- Em qual valor de n o “menos eficiente” supera o “mais eficiente”?
