next up previous
Next: About this document ...

MAC 5710 - Estruturas de Dados e sua Manipulação

URL: http://www.ime.usp.br/$\sim$song/mac5710.html

Eficiência ou complexidade de algoritmos

Siang - 2005

(Daremos aqui um tratamento informal sobre o assunto. Maiores detalhes devem ser obtidos em cursos de Análise de Algoritmos.)

Costuma-se analisar um algoritmo em termos de tempo e espaço (ou memória). Para o tempo, diversas medidas são em princípio possíveis:

  1. Tempo absoluto (em minutos, segundos, etc.) - não é interessante por depender da máquina.

  2. Número de operações consideradas relevantes (por exemplo comparações, operações aritméticas, movimento de dados, etc.)

Três casos podem ser considerados: o melhor caso, o caso médio e o pior caso. O estudo do caso médio depende do conhecimento ou suposição da distribuição das entradas ao problema. Em geral o pior caso é o mais fácil de se analisar.

Por exemplo, se temos 2 métodos para resolver um mesmo problema, cuja entrada tem tamanho $n$, podemos ter:

Método 1: $T_1 (n) = 2 n^2 + 5 n$ operações

Método 2: $T_2 (n) = 500 n + 4000$ operações

Dependendo do valor de $n$, método 1 pode requerer mais ou menos operações que método 2.

Notação O

Para estudarmos o comportamento assintótico - para $n$ grande - interessa-nos o termo de ordem superior:

Método 1: $T_1(n) = O(n^2)$

Método 1: $T_2(n) = O(n)$

A notação O pode ser formalizada como se segue:

Dizemos que $T(n) = O(f(n))$ se existirem inteiro $m$ e constante $c$ tais que


\begin{displaymath}T(n) \leq c f(n) \ \ \mbox{para } \ n > m.\end{displaymath}

Isto é, para valores de $n$ suficientemente grandes, $T(n)$ não cresece mais rapidamente que $f(n)$.

A importância da complexidade pode ser observada pelo seguinte exemplo, que mostra 5 algoritmos $A_1$ a $A_5$ para resolver um mesmo problema, de complexidades diferentes. Supomos que uma operação leva 1 ms para ser efetuada. A tabela seguinte dá o tempo necessário por cada um dos algoritmos. (Sempre suporemos logaritmos na base 2.)

  $A_1$ $A_2$ $A_3$ $A_4$ $A_5$
$n$ $T_1(n)=n$ $T_2(n)=n\log n$ $T_3(n)=n^2$ $T_4(n)=n^3$ $T_5(n)=2^n$
16 0.016s 0.064s 0.256s 4s 1m 4s
32 0.032s 0.16s 1s 33s 46 dias
512 0.512s 9s 4m 22s 1 dia 13h $10^{137}$ séculos


Podemos muitas vezes melhorar o tempo de execução de um programa (que implementa um algoritmo dado) fazendo otimizações locais (e.g. usar $x+x$ ao invés de $2x$, em máquinas em que a multiplicação é mais demorada que a adição).

Entretanto, melhorias substanciais são muitas vezes obtidas se usarmos um algoritmo diferente, com outra complexidade de tempo, e.g. obter um algoritmo de $O(n\log n)$ ao invés de $O(n^2)$.

Cota superior ou limite superior (``upper bound'')

Seja dado um problema, por exemplo, multiplicação de duas matrizes quadradas de ordem $n$. Conhecemos um algoritmo para resolver este problema (pelo método trivial) de complexidade $O(n^3)$. Sabemos assim que a complexidade deste problema não deve superar $O(n^3)$, uma vez que existe um algoritmo desta complexidade que o resolve. Uma cota superior (ou ``upper bound'') deste problema é $O(n^3)$. A cota superior de um problema pode mudar se alguém descobrir um outro algoritmo melhor. Isso de fato aconteceu com o algoritmo de Strassen que é de $O(n^{\log 7})$. Assim a cota superior do problema de multiplicação de matrizes passou a ser $O(n^{\log 7})$. Outros pesquisadores melhoraram ainda este resultado. Atualmente o melhor resultado é o de Coppersmith e Winograd - de $O(n^{2.376})$. Notem que a cota superior de um problema depende do algoritmo.

A cota superior de um problema é parecida com o record mundial de uma modalidade de atletismo. Ela é estabelecida pelo melhor atleta (algoritmo) do momento. Assim como o record mundial, a cota superior pode ser melhorada por um algoritmo (atleta) mais veloz.



``Cota Superior'' dos 100 metros rasos:



Ano Atleta (Algoritmo) Tempo
1988 Carl Lewis 9s92
1993 Linford Christie 9s87
1993 Carl Lewis 9s86
1994 Leroy Burrell 9s84
1996 Donovan Bailey 9s84
1999 Maurice Greene 9s79
2002 Tim Montgomery 9s78

Cota inferior ou limite inferior (``lower bound'')

As vezes é possível demonstrar que para um dado problema, qualquer que seja o algoritmo a ser usado, o problema requer pelo menos um certo número de operações. Essa complexidade é chamada cota inferior ou ``lower bound'' do problema. Veja que a cota inferior depende do problema mas não do particular algoritmo. Usamos a letra $\Omega$ em lugar de $O$ para denotar uma cota inferior.

Para o problema de multiplicação de matrizes de ordem $n$, apenas para ler os elementos das duas matrizes de entrada leva tempo $O(n^2)$. Assim uma cota inferior trivial é $\Omega(n^2)$.

Na analogia anterior, uma cota inferior de uma modalidade de atletismo não dependeria mais do atleta. Seria algum tempo mínimo que a modalidade exige, qualquer que seja o atleta. Uma cota inferior trivial para os 100 metros rasos seria o tempo que a velocidade da luz leva para percorrer 100 metros no vácuo.

Se um algoritmo tem uma complexidade que é igual a cota inferior do problema, então ele é ótimo. O algoritmo de Coppersmith e Winograd é de $O(n^{2.376})$ mas a cota inferior é de $\Omega(n^2)$. Portanto não podemos dizer que ele é ótimo. Pode ser que esta cota superior possa ainda ser melhorada. Pode também ser que a cota inferior de $\Omega(n^2)$ possa ser melhorada (isto é ``aumentada''). Muitos pesquisadores desta área dedicam seu tempo tentando encurtar este intervalo (``gap'') até encostar uma da outra.




next up previous
Next: About this document ...
Siang Wun Song
2005-01-11