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 ?

1. O que é Análise de Algoritmos ?

Dado um certo de problema P queremos descobrir duas coisas:


2. O que é limitante inferior de um problema ?

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


3.O que é a função complexidade ?

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.


4. Quais são os três tipos de análise que aplicamos a um algoritmo A ?

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


5. Como determinar a função complexidade T(n) para um dado algoritmo ?

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 IK resume-se a contar quantas operações básicas são realizadas, ou seja T(|IK|), onde |IK| é o tamanho da entrada IK não importando a permutação de IK.

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.


6. O que é representação assintótica ? (aka.: O que é a tal função big-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,n0 tais que f(n)<=c*g(n) para todo n>n0
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 n0 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.

Definições das demais notações podem ser encontradas nestas notas de aula do Prof.Rebelsky.
Por que é importante a análise assintótica ?

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.


Por que é importante a análise de algoritmos ?

A análise de algoritmos é importante para:

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