\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}