modelos.tex

\chapter{Modelos}

Vimos no Capítulo \ref{} que podemos avaliar o tempo de processamento de um algoritmo usando o método empírico.
Para isso, em algum momento precisamos de um {\em modelo} que iremos testar.
Nos exemplos que vimos o modelo foi tirado intuitivamente a partir das observações.
Há métodos mais adequados para conceber um modelo para o consumo de tempo de um algoritmo.

Vamos mais uma vez considerar os algortimos de busca que temos estudado.

\begin{codebox}
\Procname{$\proc{BuscaSequencial}(A, b)$}
\li \For $i \gets 1$ até $n$
\li \Do \If $a_i = b$
\li     \Then \Return $i$
        \End
    \End
\li \Return $\bot$
\End
\end{codebox}

Quando esse algoritmo for implementado e executado em uma máquina, as instruções seguidas tomarão um tempo que depende de uma série de fatores.
Vamos seguir a suposição razoável que instruções iguais tomarão o mesmo tempo em uma mesmo contexto.
Assim, podemos supor, por exemplo, que:
\begin{itemize}
\item incrementar uma variável (linha 1) toma tempo $c_1$
\item comparar duas variáveis (lina 2) toma tempo $c_2$
\item devolver um valor (linhas 3 e 4) toma tempo $c_3$
\end{itemize}

Os valores de $c_1$, $c_2$ e $c_3$ deve ser diferente a depender do contexto, mas vamos supor que sejam {\em constantes} em um mesmo contexto.
Fazendo essa suposição, vamos então contar quantas vezes cada uma dessas operações é feita.

O número de repetições depende de duas coisas: o tamanho da entrada ($n$) e os valores da entrada.
Gostaríamos de um modelo que dependesse apenas do tamanho da entrada.
Podemos fazer dois tipos de análises para abstrair os valores da entrada:
\begin{itemize}
\item {\em análise de caso médio}: nos dá um valor mais preciso, mas depende da distribuição de probabilidade da entrada ou
  \item {\em análise de pior caso}: nos dá um valor menos preciso, mas ainda assim bastante útil e não depende de nenhuma suposição sobre os valores da entrada.
  \end{itemize}

Nos focaremos em análises de pior caso porque na maioria das vezes não sabemos de antemão a distribuição de probabilidade da entrada.

Vamos contar o número de repetições de cada operação assumindo o pior caso:
\begin{itemize}
\item a atualização da variável $i$ na linha 1 se repete $n$ vezes,
\item a comparação na linha 2 se repete $n$ vezes no pior caso e
\item as linhas 3 e 4 ocorrem uma única vez ao todo durante toda a execução.
\end{itemize}

Podemos então construir o seguinte modelo para o tempo de processamento do algoritmo no pior caso em função do tamanho $n$ da entrada:

\begin{displaymath}
  t(n) = c_1n + c_2n + c_3 = (c_1 + c_2)n + c_3
\end{displaymath}

O mesmo modelo que extraímos das observações no Capítulo \ref{}.

Vamos agora replicar esse mesmo tipo de análise para nosso outro algoritmo.
\begin{codebox}
  \Procname{$\proc{BuscaBinaria}(A, b)$}
  \li $i \gets 1$
  \li $j \gets |A|$
  \li \While $i \leq j$
  \li \Do $m \gets \left \lfloor{\frac{j+i}{2}}\right\rfloor$
  \li \If $b < a_m$
  \li     \Then $j \gets m - 1$
  \li \Else
      \If $b > a_m$
  \li      \Then $i \gets m + 1$
  \li \Else \Return m 
      \End
  \End
  \End
  \li \Return $\bot$
\end{codebox}

O primeiro passo é atribuir constantes para o tempo de processamento de cada operação atômica:
\begin{itemize}
\item $c_1$ para as atribuições nas linhas 1 e 2,
\item $c_2$ para as comparações nas linhas 3, 5 e 7,
\item $c_3$ para a divisão na linha 4,
\item $c_4$ para o incremento e decremento nas linhas 6 e 8 e
\item $c_5$ para devolver um valor nas linhas 9 e 10.
\end{itemize}

Agora vamos contar o número de vezes que cada linha é executada no pior caso.
As linhas 1 e 2 são executadas uma vez cada.
As linhas 9 e 10 são executadas uma vez ao todo.
Já as linhas 3 a 6 são executadas enquanto $i \leq j$.

Para avaliar quantas vezes as linhas 3-6 são executadas, vamos primeiro supor que o tamanho da sequência é uma potência de $2$ e, portanto, existem $x$ tal que:

\begin{displaymath}
  n = 2^x \Rightarrow x = log_2(n)
\end{displaymath}

O pedaço da sequência que nos interessa é $a_i, \dots, a_j$ -- na prova da correção vimos $b$ nunca está no outro pedaço da sequência.
Note agora que a cada passo o tamanho dessa sequência diminui pela metade.
Ele começa sendo $n = 2^x$, cai para $\frac{n}{2} = 2^{x-1}$ na segunda iteração e assim consecutivamente até chegar em $1 = 2^0$.
Precisamo de $x$ passos para chegar no último passo.

Assim, temos o seguinte modelo para o tempo e processamento do algoritmo:

\begin{displaymath}
  t(2^x) = 2c_1 + c_5 + x(3c_2 + c_3 + c_4)
\end{displaymath}

Aplicando a mudança de variável, temos que:

\begin{displaymath}
  t(n) = (3c_2 + c_3 + c_4)log_2(n) + 2c_1 + c_5
\end{displaymath}

O mesmo modelo que obtivemos no Capítulo \ref{} a partir das observações.

\begin{exercicio}
Considere o seguinte algoritmo $3Soma$ apresnetado no final do capítulo anterior.
Calcule o tempo de processamento em função do tamanho $n$ da entrada assumindo que:

\begin{itemize}
\item Cada iteração de variável toma tempo constante $c_1$
\item Cada atribuição toma tempo constante $c_2$
\item Cada soma toma tempo constante $c_3$
\item A saída toma tempo constante $c_4$
\end{itemize}
  
\end{exercicio}