Análise de Algoritmos - FAQ

1. O que é Análise de Algoritmos ?
2. O que é limitante inferior de um problema ?
3. O que é função complexidade ?
4. Quais são os três tipos de análise que aplicamos a um algoritmo A ?
5. Como determinar a função complexidade T(n) para um dado algoritmo ?
6. O que é representação assintótica ? (aka.: O que é a tal função big-O?)
7. Por que é importante a análise assintótica ?
8. Por que é importante a análise de algoritmos ?

Dado um certo de problema P queremos descobrir duas coisas:

• Qual função representa o limitante inferior para a resolução do problema P.
  Ou seja, qualquer que seja o Algoritmo escolhido sua função complexidade será equivalente
  ou pior que o limitante inferior.
• Dado um Algoritmo A que resolve o problema P, qual a função complexidade deste algoritmo ?
  Se a complexidade de A for equivalente em ordem de grandeza ao limitante inferior do problema, então
  podemos dizer que o algoritmo A é ótimo.

É uma medida que expressa a ordem de grandeza da dificuldade de se resolver um problema P, não levando em consideração nenhum algoritmo em particular. Também pode-se dizer que o limitante inferior determina a fronteira da otimalidade para todo e qualquer algoritmo (conhecido ou desconhecido!) que resolva o problema P no pior caso.

Cuidado: O limitante inferior é definido com base no pior caso do problema, onde por pior caso se entende o caso mais díficl de ser resolvido. O lado zen é que o limitante inferior é também uma medida para o algoritmo ótimo que resolve o problema P. É quase um poema hai-kai.

A função complexidade T(n) estabelece uma relação entre o tamanho da entrada I=|n| de um dado algoritmo A e o tempo que A leva para processar esta entrada.

A função complexidade pode ser determinada para três casos particulares de um dado algoritmo A:

• melhor caso: escolhemos a entrada I_K dentre todo o conjunto de entradas possíveis que favorece a execução do algoritmo A, implicando no menor cosumo de tempo para execução.
• pior caso: escolhemos a entrada I_K dentre todo o conjunto de entradas possíveis que desfavorece a execução do algoritmo A, implicando no maior cosumo de tempo para execução.
• caso médio : escolhemos todas as entradas I possíveis ou uma distribuição de probabilidade adequada para as entradas I, calculamos o tempo consumido para cada entrada I_K e calculamos a média ponderada de acordo com a probabilidade de ocorrência de cada entrada.

Baseando-se no código-fonte (ou pseudo-código) do algoritmo, identificamos as operações que são representativas do esforço que o algoritmo A faz na resolução do problema P. As operações representativas são então denominadas de operação básica.

Cada ocorrência da operação básica equivale a 1 unidade de medida de complexidade (hipótese do custo uniforme). Analisar o algoritmo para uma dada entrada I_K resume-se a contar quantas operações básicas são realizadas, ou seja T(|I_K|), onde |I_K| é o tamanho da entrada I_K não importando a permutação de I_K.

Encontraremos três funções: uma para o melhor caso, uma para o pior caso, e uma para o caso médio. As funções encontradas podem ser idênticas ou não.

Como as equações que descrevem o comportamento de um dado algoritmo A podem ser muito complexas, varias simplificações podem ser aplicadas. Desta forma, uma expressão exata para a função complexidade T(n) pode não ser encontrada, entretanto talvez seja possível determinar limitantes para T(n), ou seja :

T'(n) < T(n) < T''(n)

Formalizando estes conceitos temos as seguintes relações definadas para uma função qualquer f(n):

f(n)=O(g(n)) .: se existem constantes c,n₀ tais que f(n)<=c*g(n) para todo n>n₀
Esta definição diz que f(n) está limitada superiormente pela família de funções função c*g(n) a partir de um n₀ suficientemente grande.
Outra forma de definir a relação

f(n)=O(g(n)) sse infinito > lim [f(n)/g(n)] >= 0 quando n -> infinito.

A análise assintótica permite comparar funções complexidades T(n) de diferentes algoritmos, agrupando-as em classes de equivalência. Logo, dado um problema P que possua uma coleção de algoritmos {A} que o resolvam, é possível escolher aqueles que sejam mais eficientes com base na determinação de suas funções complexidade. Ou seja, a análise assintótica é a simplificação matemática que viabiliza a análise de algoritmos.

A análise de algoritmos é importante para:

• Determinar se um algoritmo A que resolve o problema P é ótimo ou não.
• Comparar a eficiência de diferentes algoritnos
• Determinar a escalabilidade de uma dada implementação, ou seja, como ela se comportará quando o conjunto de entradas crescer.

Para ilustar o último tópico convém analisar a tabela de crescimento de algumas funções típicas.