\documentclass[10pt]{article}


\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}

\setlength{\unitlength}{28pt}
\setlength{\textwidth}{15cm}
\setlength{\textheight}{23.5cm}
\setlength{\oddsidemargin}{0.1in}
\setlength{\evensidemargin}{0.1in}
\voffset=-2.5cm
\hoffset=1cm
\newcommand{\p}{\vspace{1.44ex}}
\font\eucl=/home/mac/song/brasao/ime scaled 1000 %era 700 %%%%%%%%%%%
%\font\eucl=brasao-ime scaled 700 %860
\font\usp=cmbx10 scaled \magstep1  %nao funciona no latex ????
\font\ime=cmr10
\font\cp=cmr9
\font\ll=cmss10


\begin{document}

\noindent
{\bf \large MAC 5710 - Estruturas de Dados e sua Manipulação}

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

\noindent
{\bf \large Efici\^encia ou complexidade de algoritmos}

\begin{flushright}
Siang - 2005
\end{flushright}

(Daremos aqui um tratamento informal sobre o assunto. Maiores
detalhes devem ser obtidos em cursos de An\'alise de Algoritmos.)
\p

Costuma-se analisar um algoritmo em termos de tempo e espa\c{c}o
(ou mem\'oria). Para o tempo, diversas medidas s\~ao 
em princ\'{\i}pio poss\'{\i}veis:

\begin{enumerate}
\item Tempo absoluto (em minutos, segundos, etc.) -- n\~ao
\'e interessante por depender da m\'aquina.

\item N\'umero de opera\c{c}\~oes consideradas relevantes
(por exemplo compara\c{c}\~oes, opera\c{c}\~oes aritm\'eticas,
movimento de dados, etc.)
\end{enumerate}

Tr\^es 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.
\p

Por exemplo, se temos 2 m\'etodos para resolver um
mesmo problema, cuja entrada tem tamanho $n$, podemos
ter:
\p

M\'etodo 1: $T_1 (n) = 2 n^2 + 5 n$ opera\c{c}\~oes

M\'etodo 2: $T_2 (n) = 500 n + 4000$ opera\c{c}\~oes
\p

Dependendo do valor de $n$, m\'etodo 1 pode requerer mais
ou menos opera\c{c}\~oes que m\'etodo 2.

\noindent
{\bf \large Nota\c{c}\~ao O}

Para estudarmos o comportamento assint\'otico -- para $n$ grande --
interessa-nos o termo de ordem superior:
\p

M\'etodo 1: $T_1(n) = O(n^2)$

M\'etodo 1: $T_2(n) = O(n)$
\p

A nota\c{c}\~ao O pode ser formalizada como se segue:

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

$$ T(n) \leq c f(n) \ \ \mbox{para } \ n > m.$$

Isto \'e, para valores de $n$ suficientemente grandes, 
$T(n)$ n\~ao cresece mais rapidamente que $f(n)$.
\p

A import\^ancia 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\c{c}\~ao leva 1 ms para ser
efetuada. A tabela seguinte d\'a o tempo necess\'ario por
cada um dos algoritmos. (Sempre suporemos logaritmos na base 2.)
\p

\begin{tabular}{c|ccccc}
    & $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$                                     \\ \hline
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\'eculos                             \\
\end{tabular}
\p

Podemos muitas vezes melhorar o tempo de execu\c{c}\~ao de um
programa (que implementa um algoritmo dado) fazendo otimiza\c{c}\~oes
locais (e.g. usar $x+x$ ao inv\'es de $2x$, em m\'aquinas
em que a multiplica\c{c}\~ao \'e mais demorada que a adi\c{c}\~ao).
\p

Entretanto, melhorias substanciais s\~ao 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\'es de 
$O(n^2)$.

\noindent
{\bf \large Cota superior ou limite superior (``upper bound'')}

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

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

\p

``Cota Superior''  dos 100 metros rasos:

\p

\begin{tabular}{lll}
Ano   & Atleta (Algoritmo) & Tempo \\
\hline
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  \\
\end{tabular}


\noindent
{\bf \large Cota inferior ou limite inferior (``lower bound'')}

As vezes \'e poss\'{\i}vel demonstrar que para um dado problema,
qualquer que seja o algoritmo a ser usado, o problema
requer pelo menos um certo n\'umero de opera\c{c}\~oes.
Essa complexidade \'e chamada cota inferior ou ``lower bound''
do problema. Veja que a cota inferior depende do problema
mas n\~ao do particular algoritmo. Usamos a letra $\Omega$
em lugar de $O$ para denotar uma cota inferior.
\p

Para o problema de multiplica\c{c}\~ao 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 \'e $\Omega(n^2)$.
\p

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.
\p

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



\end{document}

