intr_prog/introducao_eficiencia_algoritmos.html

<!--
 Introdução à Programação - 2017 - Prof. Leoônidas de Oliveira Brandão
 Introdução à eficiência de algoritmos
 LInE (Laboratory of Informatics in Education) - http://www.usp.br/line
 IME - USP
 Material didático
 Pode usar livrevemente este material para fins não comerciais, devendo sempre fazer referência à autoria.
 Sugestões/apontamento são bem vindos: leo@ime.usp.br (favor indicar no assunto "material de introducao 'a programacao")
 Prof. Leônidas de Oliveira Brandão
 http://www.ime.usp.br/~leo
 http://line.ime.usp.br
 http://www.matemtica.br
-->

  <meta http-equiv='Content-Type' content='text/html; charset=UTF-8'>
  <meta name='keywords' content='mac0122, material, professores, leonidas de oliveira brandao'>
  <link rel='stylesheet' type='text/css' href='css_img_js_conf/all.css'>
  <link rel='stylesheet' type='text/css' href='css_img_js_conf/line_introducao_programacao.css'>
  <script src="css_img_js_conf/defineLInE.js"></script> <!-- para referencias 'a documentos internos -->
<div class="pagina">

        
<p class="secao">Introdução à eficiência de algoritmos</p>

<center><p>[
  <a href="#precisao" title="Problema de precisao numerica">Precisão</a> &nbsp; | &nbsp; 
  <a href="#tempo" title="Eficiencia em relacao ao tempo de execucao">Velocidade</a> &nbsp; | &nbsp; 
  <a href="#cosseno" title="Eficiencia: examinando a funcao transcendente <i>cosseno</i>">Cosseno</a> &nbsp; | &nbsp; 
  <a href="#muitoingenuo" title="Uma primeira solucao nada eficiente para a funcao <i>cosseno</i>">Solução ineficiente</a> &nbsp; | &nbsp; 
  <a href="#ingenuo" title="Uma segunda solucao para a funcao <i>cosseno</i>: ainda ineficaz">Solução</a> &nbsp; | &nbsp; 
  <a href="#eficiente" title="Uma solucao eficiente para a funcao <i>cosseno</i>">Solução eficiente</a>
 ]</p>
</center>

<!--
<p>
<b>Alterações</b>: //2017  <i>C</i> e <i>Python</i>)
</p>
-->

<p>
  Nesta seção examinaremos uma questão essencial à computação, se o algoritmo é ou não eficiente para resolver o problema de interesse.
  Sobre isso existem vários aspectos que podem ser considerados, aqui examinaremos dois: a <b>precisão</b> e a <b>velocidade</b>.
  <center>
  <img src="img/img_precisao_x_velocidade.png" title="Gráfico ilustrando que geralmente precisão varia inversamente com a velocidade"/>
  <br/>
  <i>Fig. 1. Representação de que maior velocidade de execução geralmente implica em menor precisão numérica.</i>
</center>

</p>

<p>
  A <b style="color:#0000aa;">precisão</b> diz respeito à "qualidade" da resposta, é necessário que ela seja
  <b style="color:#00aa00;">suficientemente próxima da real solução</b> para o problema considerado.
  Para ilustrar podemos considerar um exemplo <i>numérico</i>, por exemplo, tentar encontrar a raíz para determinada
  função <i>f(.)</i>, ou seja, encontrar (se existir) algum <i>x</i> para o qual <i>f(x)=0</i>.
  Nesse caso, se o interesse estiver em pontos dentro do intervalo <i>[0, 1]</i>, seria inútil se o ponto devolvido
  tivesse um <i style="color:#aa0000;" title="pois se a resposta foi 1/2, na verdade a raíz poderia ser desde o ponto 0 até o ponto 1!">erro
  maior que <i>0,5</i></i> (i.e., <i>|f(x)| > 0,5</i>).
  <br/>
  Outro exemplo numérico é computar uma
  <a href="https://pt.wikipedia.org/wiki/Fun%C3%A7%C3%A3o_transcendente" target="_blank"
     title="função que não pode ser escrita com operações algébricas - ver na WikiPedia">função transcendente</a> como o <i>cosseno</i> de valor real.
  Uma vez as operações que um computador digita consegue efetivamente realizar são aquelas diretamente derivadas da soma, é preciso encontrar um
  algoritmo que compute uma <i>boa aproximação</i> para o <i>cosseno(x)</i>, qualquer que seja o valor real <i>x</i>.
  Neste texto examinaremos as implementações para as funções <i>seno</i> e <i>cosseno</i> empregando o conceito matemático
  <a href="https://pt.wikipedia.org/wiki/S%C3%A9rie_de_Taylor" target="_blank">
  <b style="color:#00aa00;"
     title="um somatório com infinitos termos que aproxima a função por meio de um
  polinômio cuja propriedade é que suas derivadas, de todas as ordens, 
  coincidem com as derivadas da função aproximada no ponto dado">série de Taylor</b></a>. <!-- " -->
</p>

<p>
  Quanto à <b style="color:#0000aa;">velocidade</b>, ela diz respeito ao <i>tempo que o algoritmo leva para computar a resposta</i>.
  É preciso que o tempo seja viável para o contexto, quer dizer que ao obter a resposta, essa ainda seja útil.
  Para ilustrar podemos considerar novamente o exemplo <i>numérico</i> da determinação da raíz da função <i>f(.)</i> (se existir, encontrar
  algum <i>x</i> para o qual <i>f(x)=0</i>).
  Digamos que o interessado seja uma industria de produção de tintas e que a raíz representa o melhor momento para interromper a
  produção de cada um de seus 300 pigmentos distintos.
  Nesse caso, se a resposta para cada função/pigmento demorar cerca de 10 minutos, então o método empregado é
  inviável, pois seria <i style="color:#aa0000;" title="pois levaria mais de 2 dias para obter a produção ideal para aquele dia!">necessário
  cerca de 50 horas para obter as 300 raízes</i> (<i>50 x 10 min = 3000 min</i>).
  <br/>
  Um exemplo de outra natureza seria o contexto de planejamentos de pousos e aterrissagens em um grande aeroporto, após a ocorrência
  de algum evento não esperado, deve-se gerar uma nova escala para as próxima
  aterrissagens e decolagens muito rapidamente, antes que acabe o combustível de alguma aeronave em sobrevoo.
  
</p>


<a name="precisao">
<p class="secao">Problema de precisão numérica</p>
</a>

<p>
  Como discutido no <a href="#" onclick="trocaPagina('introducao_float.html')" title="examinar o texto sobre ponto flutuante">texto sobre
  <i>ponto flutuante</i></a>, o problema de precisão numérica inicia-se na impossibilidade de representar valores
  <i style="color:#00aa00;" title="Impossível representar todos os dígitos de Pi (pois são infinitos)!">irracionais</i>
  e mesmo
  <i style="color:#00aa00;" title="Impossível representar todos os dígios de 1/3 (pois são infinitos)!">dizimas periódicas</i> que precisam
  ser <b style="color:#0000aa;" title="Por exemplo, representar 1/3 por 0,3333 (truncando na quarta casa decimal)">truncados</b>.
  Mas existe outra questão de eficiência, que é a precisão numérica do algoritmo utilizado para o cômputo.
  Um exemplo ilustrativo é acumular valores que crescem muito rapidamente (como funções exponenciais ou fatoriais) ou
  dividir por valores que aproximam-se de zero, ambos podem produzir resultados "ruins":
  <b style="color:#0000aa;" title="estourar o maior valor que o computador tem capacidade para representar (overflow)">estouro</b>
  (ou <i>transbordamento</i>).
</p>

<p>
  Como citado acima, um problema computacional é conseguir implementar funções que não podem ser escritas a partir de operações elementares
  de soma e multiplicação, com é o caso da função <i>cosseno</i> (que por isso é transcendental).
  Hoje, este não parece ser um problema, pois qualquer computador de bolso tem uma calculadora implementada que é capaz de computar boas
  aproximações para a função <i>cosseno</i>.
  Entretanto, isso só é possível por implementarem algum algoritmo eficiente, a partir de somas e multiplicações.
  No caso das <i>funções trigonométicas</i>, isso é feito usando a técnica matemática da
  <i title="Na verdade com um truque para tratar todos os períodos">série de Taylor</i>.
  Isso será ilustrado nas tabelas <a href="#solucaoruim" title="seguir para implementação ruim">1 (implementação ineficiente)</a>
  e <a href="#solucaoboa" title="seguir para implementação boa">2 (implementação eficiente)</a>.
</p>


<a name="tempo">
<p class="secao">Eficiência em relação ao tempo de execução</p>
</a>

<p>
  Existem problemas que sabidamente são intratáveis no sentido de sabermos, matematicamente, que é impossível existir
  um algoritmo que consegue resolvê-lo (como o <i>problema da parada</i>: não existe algoritmo que possa decidir se um algoritmo qualquer pára ou
  após um tempo finito de execução).
</p>

<!--p class="sabermais" title="Para quem deseja saber um pouco mais 'como funciona'"-->
<p><sabermais title="Para quem deseja saber um pouco mais 'como funciona'">
  Existem outros tipos de problemas que supomos <b style="color:#aa0000;">não</b> ser possível resolvê-los eficientemente, ou seja,
  todas suas soluções conhecidas são ineficientes
  (tempo proporcional à uma função exponencial, de base maior que a unidade).
  Um exemplo nessa categoria, que denominada
  <a href="https://en.wikipedia.org/wiki/NP-completeness" target="_blank" title="Examinar texto na WikiPedia em Inglês">NP-Completo</a>, é o
  <a href="https://pt.wikipedia.org/wiki/Problema_de_satisfatibilidade_booliana" target="_blank"
     title="examinar a explicação na WikiPedia sobre o problema da satisfatibilidade"><i>problema da satisfatibilidade</i></a>:
  encontrar valores para cada uma de suas variáveis, que são <i>booleanas</i>, de modo a tornar a expressão lógica verdadeira,
  como em <i>f(b<sub>1</sub>, b<sub>2</sub>, b<sub>3</sub>) = b<sub>1</sub> E (b<sub>2</sub> OU não b<sub>3</sub>)</i>.
  Para esse caso, por ser uma instância pequena do problema, é fácil perceber que a resposta é <i>sim</i>, basta tomar
  <i>b<sub>1</sub></i> e <i>b<sub>2</sub></i> como <i>verdadeiro</i> (não importando o valor de <i>b<sub>3</sub></i>
  pode ser <i>verdadeiro</i> ou <i>falso</i>).
  A solução conhecida para a <i>satisfatibilidade</i> é tentar todas as <i>2<sup>n<sup></i> possibilidades para as <i>n</i>
  variáveis! Se o <i>n</i> for grande, é inviável esperar por uma resposta.
  Exemplo para <i>n=3</i>: testar com
  <codigo2>  &nbsp; &nbsp; <i>f(verdadeiro,verdadeiro,verdadeiro)</i>, <i>f(verdadeiro,verdadeiro,falso)</i>,
  &nbsp; &nbsp; <i>f(verdadeiro,falso,     verdadeiro)</i>, <i>f(verdadeiro,falso,     falso)</i>,
  &nbsp; &nbsp; <i>f(falso,     verdadeiro,verdadeiro)</i>, <i>f(falso,     verdadeiro,falso)</i>,
  &nbsp; &nbsp; <i>f(falso,     falso,     verdadeiro)</i>, <i>f(falso,     falso,     falso)</i>.</codigo2>
</sabermais>
</p>

<p>
  Na seção seguinte examinaremos um particular problema, conseguir um valor aproximado para a função trigonométrica <i>cosseno</i>,
  explorando tanto a questão da eficiência numérica (precisão) quanto a de tempo de execução (velocidade).
</p>


<a name="cosseno">
<p class="secao"><i>Série de Taylor</i> e a função <i>cosseno</i></p>
</a>

<p>
  A função <i>cosseno</i>, assim como várias outras, não pode ser computada de modo exato em um computador digital,
  em razão de ser uma
  <a href="https://pt.wikipedia.org/wiki/Função_transcendente" title="sobre funcao transcendente">função <i>transcendente</i></a>
  (basicamente, significa que não pode ser computada a partir de somas).
  Então usamos uma
  <a href="https://en.wikipedia.org/wiki/Taylor_series" target="_blank"
     title="examinar a explicação na WikiPedia sobre séries de Taylor">teoria matemática apresentada em 1715</a>,
  aproximá-la por uma função polinomial que tem como propriedade ter todas as derivadas
  coincidindo com as derivadas da função a ser aproximada, considerando determinado ponto fixado.
  Esse polinômio de infinitos termos, recebeu o nome de
  <a href="https://pt.wikipedia.org/wiki/S%C3%A9rie_de_Taylor" title="sobre serie de Taylor na WikiPedia"><b>série de Taylor</b></a>,
  devido seu proponente Brook Taylor.
</p>

</p>
  O <i>polinômio de Taylor</i> que aproxima a função cosseno quando aplicada ao ponto <i>x</i> é:
  <center>
   <i>cos(x) = 1 - x<sup>2</sup> /2! + x<sup>4</sup> /4! - x<sup>6</sup> /6! + x<sup>8</sup> /8! + ...</i>
  </center>
  Se estiver interessado entender a Matemática para se construir a demostração desse polinômio, estude o bloco abaixo.
<p>

<p>
<sabermais title="Para quem deseja saber um pouco mais: mas precisa conhecer Cálculo Diferencial">
  Como a função <i>cosseno</i> é periódica, de período <i title="letra grega Pi, representa a irracional 3.1415926535897932384626433...">2*&Pi;</i>
  e além disso os valores em cada quadrante coincidem em módulo, podemos computar apenas para primeiro caso, para <i>x</i> entre
  <i>0</i> e <i>&Pi;/2</i>.
  <img class="imgDir" src="img/img_eficiencia_cos_trig.png" title="Imagem (do iGraf) da função trigonométrica cosseno indicando o período 2*&Pi;">
  Desse modo, podemos usar um caso particular da <b>série de Taylor</b>, a séria aplicada ao ponto <i>x=0</i>, que neste caso é chamada
  de
  <a href="https://en.wikipedia.org/wiki/Colin_Maclaurin"
     title="sobre serie de MacLaurin na WikiPedia"><b style="color:#0000aa">série de MacLaurin</b></a>.
  Fixado um valor real <i>x</i> entre <i>0</i> e <i title="letra grega Pi, representa a irracional 3.1415926535897932384626433...">&Pi;/2</i>,
  a <i>série de MacLaurin</i> que aproxima o cosseno aplicado ao ponto <i>x=0</i>, <i>cos(x)</i>, é o polinômio (de infinitos termos)
  
  <i>p(x)=a<sub>0</sub>+a<sub>1</sub>x<sup>1</sup>+a<sub>2</sub>x<sup>2</sup>+a<sub>3</sub>x<sup>3</sup>+...</i>

  de tal forma que
  a <i>k</i>-ésima derivada de <i>p(0)</i> coincide com a <i>k</i>-ésima derivada de <i>cos(0)</i>, ou seja,
  <i>cos(0)=p(0)</i>, <i>cos'(0)=p'(0)</i>, <i>cos''(0)=p''(0)</i> e assim por diante.
<br/>
<br/>
  Assim, no caso da função cosseno, escrevendo o polinômio candidato
  <i>p(x) = a<sub>0</sub> x<sup>0</sup> + a<sub>1</sub> x<sup>1</sup> + a<sub>2</sub> x<sup>2</sup> +...</i>
  e estabelecendo as identidades para cada derivada e usando <i>x=0</i> e sabendo que
  <i>cos(0)=1</i>, <i>sen(0)=0</i>, que
  <i>cos'(x)=-sen(x)</i> e que <i>sen'(x)=cos(x)=</i>, obtém-se
  <br/>
  &nbsp; &nbsp; <i>p(0)=a<sub>0</sub>
    &rArr; a<sub>0</sub> = 1<br/>
  &nbsp; &nbsp; <i>p'(0)=a<sub>1</sub>+2a<sub>2</sub>x<sup>1</sup>+3a<sub>3</sub>x<sup>2</sup>+...</i>|x=0
    &rArr; p'(0)=a<sub>1</sub>
    &rArr; a<sub>1</sub> = p'(0)= -sen(0) = 0
    &rArr; a<sub>1</sub> = 0<br/>
  &nbsp; &nbsp; <i>p''(0)=2a<sub>2</sub>+6a<sub>3</sub>x<sup>1</sup>+12a<sub>4</sub>x<sup>2</sup>+...</i>|x=0
    &rArr; (1/2)p''(0)=a<sub>2</sub>
    &rArr; a<sub>2</sub> = (1/2)(-cos(0)) = -1
    &rArr; a<sub>2</sub> = -1/2<br/>
  &nbsp; &nbsp; <i>p'''(0)=6a<sub>3</sub>+24a<sub>4</sub>x<sup>1</sup>+...</i>|x=0
    &rArr; (1/6)p'''(0)=a<sub>3</sub>
    &rArr; a<sub>3</sub> = (1/6)(cos'''(0)) = (1/3!)(-sen''(0)) = (1/3!)(-cos'(0)) = (1/3!)sen(0) = (1/3!)0
    &rArr; a<sub>3</sub> = 0<br/>
  e assim, por diante, obtendo-se o polinômio aproximador:
  <br/>
  &nbsp; &nbsp; &nbsp; &nbsp;
  <i>cos(x) = 1 - x<sup>2</sup> /2! + x<sup>4</sup> /4! - x<sup>6</sup> /6! + x<sup>8</sup> /8! + ...</i>
</sabermais>
</p>

<!--
&rArr; = implica
&sime; aproximado
&check;
 -->

<a name="cosseno">
<p class="secao">Eficiência: examinando a função transcendente <i>cosseno</i></p>
</a>

<p>
  A implementação da aproximação da função <i>cosseno</i>, próximo do valor nulo, por <i>série de Taylor</i> produz um bom exemplo
  para ilustrar <i>ineficiência</i> e <i>eficiência</i> de algoritmos, quanto ao tempo de execução e quanto à precisão numérica.
  Uma primeira observação é que é necessário truncar a série por duas razões:
  é impossível computar infinitos termos; além disso a partir de determinado termo, todos os seguintes resultam zero (devido à
  precisão finita de qualquer computador).
  Portanto, devemos <i>truncar</i> a <i>série de Taylor</i>.
</p>

<p>
  Analisando o polinômio de Taylor para o <i>cosseno</i>, talvez um aprendiz na arte da programação perceba
  que é possível escrever cada termos do somatório com
  <i>(-1)<sub>k</sub>(1/2k!)x<sup>2k</sup></i>, <i>k=0,1,2,...</i>.
  Ou seja, cada termo tem no numerador um cálculo de exponencial (<i>x<sup>2k</sup></i>) e no denominador um cálculo de fatorial (<i>2k!</i>).
  Daí poderia-se desenhar um laço acumulando cada um desses termos.
  <br/>
  Entretanto, essa solução tem um claro problema (que aparecerá no primeiro teste):
  o computo de exponencial (se maior que um) e de fatorial, ambos crescem muito rápido!
  Isso resultará em valores nada próximos do esperado.
  Isso é ilustrado abaixo.
</p>


<a name="taylor">
<p class="secao">Uma primeira solução nada eficiente para a função <i>cosseno</i></p>
</a>

<p>
A partir da série de Taylor para o cosseno, percebe-se que pode-se elaborar um laço que a cada passo computa um dos termos da série, primeiro
<i>1=x<sup>0</sup>/0!</i>, depois <i>x<sup>2</sup>/2!</i> e assim por diante, para um passo genérico <i>k</i> seria,
<i>-1<sup>k</sup>x<sup>2k</sup>/(2k!)</i>.
</p>

<p>
Desse modo uma primeira solução, seria  implementar duas funções auxiliares, uma para computar a potência (<i>pot</i>) e uma para o
fatorial (<i>fat</i>), a cada passo invocando as funções auxiliares.
Vamos simplificar a condição de parada, fixando a <i>priori</i> o número de termos calculados, digamos <i>NT=10</i>.
<center>
<a name="solucaoruim">
<i>Tab. 1. Uma implementação muito ineficiente para a Série de Taylor que aproxima <i>cosseno</i>.</i>
</a>
<br/>
<table class="tbCodeLinCol">
 <tr class="tbCodeLinColH"><th colspan="2">Algoritmo muito ineficiente para cômputo do cosseno</th></tr>
 <tr><th>C </th> <th>Python</th></tr>
 <tr valign="top"><td><table class="tbCode">
   <tr><td><pre>i = 0;
while (i&lt;2*NT) { <cyan>// Ineficiente! Nao implemente assim!</cyan>
     soma = soma + pot(-1, 2*i) * pot(x, 2*i) / fat(2*i);
     i += 2;
     }</pre></td></tr>
 </table></td>
 <td><table class="tbCode"><pre>i = 0;
while (i&lt;2*NT) : <cyan># Ineficiente! Nao implemente assim!</cyan>
     soma = soma + pot(-1, 2*i) * pot(x, 2*i) / fat(2*i);
     i += 2;
     
  return soma;</pre></td></tr>
   </table></td></tr>
</table></center>
<p>

<p>
  Testando-se o algoritmo acima, percebe-se rapidamente que o método não é eficiente. Por exemplo, examinando a tabela 1, na qual listamos
  os resultados para vários valores de <i>x</i> empregando o método acima, um método eficiente (vistao abaixo) e a função <i>cosseno</i>
  da biblioteca da linguagem.
  Nota-se que já na segunda linha, para <i>x=0.05</i>, o método ineficiente gera o valor <i>1.0012</i> enquanto o eficiente e a biblioteca
  <i>0.9988</i>, uma diferença nada desprezível.
  Isso vai piorando com o aumento de <i>x</i>, para o último tabelado, <i>x=0.45</i>, a diferença já está em quase <i>0.2</i>!
</p>

<p>
<b>Ineficiência 1</b>.
  Fazendo um rápido exame da solução notamos um primeiro item de ineficiência:
  computar <i>pot(-1, 2*i)</i> a cada passo.
  Isso é completamente desnecessário, pois de um passo ao outro deve-se apenas inverter o sinal, então bastaria usar uma variável
  <tt>sinal</tt>,
  que a cada passo fizesse <tt>sinal = -sinal</tt>.
</p>

<p>
<b>Ineficiência 2</b>.
  Note que a mesma ineficiência do sinal ocorre com  <tt>pot</tt> e <tt>fat</tt>, pois a cada passo ignora-se que uma potência e um fatorial
  parcial já foi computado, calculando tudo desde o primeiro valor.
  Se ainda não está claro que pode ser melhorado, vamos examinar os passos <tt>k=2</tt> e  <tt>k=3</tt>:
  <br/>
  - <tt>k=2</tt>: computa-se <tt>pot(x, 2*2)=pot(x, 4)</tt> e <tt>fat(2*2)=fat(4)</tt>; e<br/>
  - <tt>k=3</tt>: computa-se <tt>pot(x, 2*3)=pot(x, 6)</tt> e <tt>fat(2*3)=fat(6)</tt>.<br/>
  Mas, se usarmos uma variável <tt>pot1</tt> para manter a potência e <tt>fat1</tt> para manter o fatorial,
  <!--
  <i>x<sup>2k</sup></i> (<tt>pot(x, 2*k)</tt>) e
  <tt>fat1</tt> para manter <i>2k!</i> (<tt>fat(2*k)</tt>),
  -->
  então, ao final do passo <tt>k=2</tt>,
  <tt>pot1</tt> estaria com o valor <i>x<sup>2k</sup>=x<sup>4</sup></i> e <tt>fat1</tt> com o valor <i>2k!=4!=24</i>.
  <br/>
  Portanto, no passo <tt>k=3</tt>, bastaria fazer:
  <center>
    <tt>pot1 = pot1 * x * x</tt> &nbsp; e &nbsp; <tt>fat1 = fat1 * 5 * 6</tt>,
  </center>
  pois dessa forma, conseguiríamos
  <center><!-- &rArr; = implica -->
    <tt>pot1 &larr; pot1 * x * x  &rArr; pot1 &larr; x<sup>4</sup> x<sup>2</sup> = x<sup>6</sup></tt> &nbsp; &nbsp; &nbsp; &nbsp; e
    <br/>
    <tt>fat1 &larr; fat1 * 5 * 6  &rArr; fat1 &larr; 4! * 5 * 6 = 6!</tt>.
  </center>
</p>

<p>
  Outro problema da solução da tabela 1 é que potência e fatorial crescem muito rápido
  (se <i>x &gt; 1</i>, mas se <i>x &lt; 1</i>, então decresce muito rápido).
  Isso também pode resultar ineficiência numérica.
</p>

<p>
  Portanto, esta solução 1 é muito ineficaz, tanto em termos de velocidade quanto de precisão.
  A discussão da razão de sua ineficácia já indica um caminho de melhoria, examinado a seguir.
</p>


<a name="ingenuo">
<p class="secao">Uma segunda solução para a função <i>cosseno</i>: ainda ineficaz numericamente</p>
</a>

<p>
Uma solução um pouco melhor, mas numericamente ainda ingênua, seria eliminar a grande ineficiência citada acima, a cada passo
aproveitando a potência e o fatorial anterior.  
Usando como critério de parada que as diferenças entre o cômputo do termo da série seja menor que um dado limiar <i>Lim</i>,
o código pode ficar como o mostrado abaixo. Suporemos a existëncia de uma função que devolve o módulo de um valor "flutuante", de nome <i>valor_absoluto</i>:
<center>
<a name="solucaomedia">
<i>Tab. 2. Uma implementação não tão ineficiente para a Série de Taylor que aproxima <i>cosseno</i>.</i>
</a>
<br/>
<table class="tbCodeLinCol">
 <tr class="tbCodeLinColH"><th colspan="2">Algoritmo ineficiente para cômputo do cosseno</th></tr>
 <tr><th>C </th> <th>Python</th></tr>
 <tr valign="top"><td><table class="tbCode">
  <tr><td><pre><verm>float</verm> cossInef (<verm>float</verm> x) {
  <verm>float</verm> pot = 1, soma = 0;
  <verm>float</verm> termo0 = 2, termo = 1;
  <verm>int</verm> fat = 1, i = 1, sinal = 1;
  while (valor_absoluto(termo0-termo)>Lim) {
     soma = soma + termo;
     pot *= x * x; <cyan>// compute potencia 2i de x</cyan>
     fat *= (i+1) * (i+2); <cyan>// compute fatorial de 2i</cyan>
     termo0 = termo;
     termo = sinal * pot / fat;
     i += 2;
     sinal = -sinal;
     }
  return soma;
  }</pre></td></tr>
 </table></td>
 <td><table class="tbCode"><pre><verm>def</verm> cossInef (x) :
  pot = 1; soma = 0;
  termo0 = 2; termo = 1;
  fat = 1; i = 0; sinal = 1;
  while (valor_absoluto(termo0-termo)>Lim) :
     soma = soma + termo;
     pot *= x * x; <cyan># compute potencia 2i de x</cyan>
     fat *= (i+1) * (i+2); <cyan># compute fatorial de 2i</cyan>
     termo0 = termo;
     termo = sinal * pot / fat;
     i += 2;
     sinal = -sinal;
  return soma;</pre></td></tr>
   </table></td></tr>
</table></center>
</p>

<p>
Rodando este algoritmo e comparando-o com a implementação interna das linguagens <b>C</b> e <b>Python</b>, mesmo para valores
próximos de zero (como <i>0.1</i>) nota-se uma diferença significativa de <i>0.01</i> (veja a tabela abaixo onde comparamos o algoritmo
acima, sua versão mais eficiente e a implementação interna da linguagem).
Isso indica que o método acima <b>não</b> é eficiente.
</p>

<p>
Analisando-se o algoritmo, percebe-se que o potencial problema é que a variável <i>termo</i> é resultado da divisão de 2 valores que tem
tem potencial de crescimento enorme (as variáveis <i>pot</i> e <i>fat</i> - com valor <i>x</i> próximo de zero,  <i>pot</i> na verdade
aproxima-se muito rápido é do zero).
<p>

</p>
Outra observação importante: a diferença entre 2 passos no laço para a variável <i>termo</i> é multiplicar por <i>x * x / (i+1)*(i+2)</i>.
Assim, poderia-se tentar a cada passo multiplicar diretamente por esta "diferença" e não acumular a potência e o fatorial!
</p>


<a name="eficiente">
<p class="secao">Uma solução eficiente para a função <i>cosseno</i></p>
</a>

<p>
Usando esta ideia produz-se o algoritmo seguinte que é bem mais eficiente. Nele aproveitamos para ilustrar o uso
de medição de tempo de execução tanto em <b>C</b> quanto em <b>Python</b>,
<center>
<a name="solucaoboa">
<i>Tab. 3. Uma implementação bem eficiente para a Série de Taylor que aproxima <i>cosseno</i>.</i>
</a>
<br/>
<table class="tbCodeLinCol">
 <tr class="tbCodeLinColH"><th colspan="2">Algoritmo eficiente para cômputo do cosseno - comparação com o ineficiente e o interno</th></tr>
 <tr><th>C </th> <th>Python</th></tr>
 <tr valign="top"><td><table class="tbCode">
  <tr><td><pre><cyan>// Leo^nidas O. Brandao - 2017/06/19</cyan>
<cyan>// cos(x) = 0! x^0 - x^2 /2! + x^4 /4! - x^6 /6! + x^8 /8! + ...</cyan>
<cyan>//        = 1 - x^2 /2! + x^4 /4! - x^6 /6! + x^8 /8! + ...</cyan>
<cyan>// gcc -lm -o introducao_eficiencia_algoritmos_cosseno introducao_eficiencia_algoritmos_cosseno.c</cyan>

<incl1>#include</incl1> &lt;stdio.h&gt;
<incl1>#include</incl1> &lt;math.h&gt; <cyan>// cos(x)</cyan>
<incl1>#include</incl1> &lt;time.h&gt; <cyan>// clock_t, clock()</cyan>

<def>#define</def> Lim 0.001

<verm>float</verm> valor_absoluto (<verm>float</verm> x) {
  if (x&gt;=0) return x;
  return -x;
  }

<cyan>// Cosseno implementado de modo ineficiente</cyan>
<verm>float</verm> cossInef (<verm>float</verm> x) { ... } <cyan>// copiar aqui o codigo C do ineficiente acima</cyan>

<cyan>// Cosseno implementado de modo mais eficiente</cyan>
<verm>float</verm> cossEfic (<verm>float</verm> x) {
  <verm>float</verm> pot = 1, soma = 0;
  <verm>float</verm> termo0 = 2, termo = 1;
  <verm>int</verm> i = 0, sinal = 1;
  while (valor_absoluto(termo0-termo)&gt;Lim) {
     soma = soma + termo;
     termo0 = termo;
     termo *= -1 * x * x / ((i+1) * (i+2)); <cyan>// compute potencia 2i de x e fatorial de 2i</cyan>
     i += 2;
     }
  return soma;
  }

<verm>int</verm> main (void) {
  <verm>float</verm> x, cosx, auxcI, auxcE;
  <verm>int</verm> i;
  clock_t tempo_inicial = clock(); <cyan>// "dispara o cronometro"...</cyan>
  <verd>printf</verd>("    x | ineficiente | eficiente | math cos(x) | dist inef. | dist efic.\n");
  x = 0.0;
  for (i=0; i&lt;10; i++) {
    cosx = cos(x);
    auxcI = cossInef(x);
    auxcE = cossEfic(x);
    <verd>printf</verd>(" %3.2f | %11.4f | %9.4f | %11.4f | %10.4f | %10.4f\n",
           x, auxcI, auxcE, cosx, valor_absoluto(auxcI-cosx), valor_absoluto(auxcE-cosx));
    x += 0.05;
    }
  clock_t tempo_final = clock();
  <verd>printf</verd>("Tempo em segundos: %f\n", (double)(tempo_final - tempo_inicial) / CLOCKS_PER_SEC);

  return 1;
  }</pre></td></tr>
 </table></td>
 <td><table class="tbCode"><pre><cyan># Leo^nidas O. Brandao - 2017/06/19</cyan>
<cyan># cos(x) = 0! x^0 - x^2 /2! + x^4 /4! - x^6 /6! + x^8 /8! + ...</cyan>
<cyan>#        = 1 - x^2 /2! + x^4 /4! - x^6 /6! + x^8 /8! + ...</cyan>

<cyan># Invocar execucao com linha de comando: python introducao_eficiencia_algoritmos_cosseno.py</cyan>

<incl1>import</incl1> math; <cyan># para cos(x)</cyan>
<incl1>import</incl1> time; <cyan># para tempo 'time.time()'</cyan>

Lim = 0.001

<verm>def</verm> valor_absoluto (x) :
  if (x>=0) : return x;
  return -x;

<cyan># Cosseno implementado de modo mais eficiente</cyan>
<verm>def</verm> cossInef (x) : <cyan># Copiar aqui a implementacao de cosseno ineficiente</cyan>
  ...
		
<cyan># Cosseno implementado de modo mais eficiente</cyan>
<verm>def</verm> cossEfic (x) :
  pot = 1; soma = 0;
  termo0 = 2; termo = 1;
  i = 0; sinal = 1;
  while (valor_absoluto(termo0-termo)>Lim) :
     soma = soma + termo;
     termo0 = termo;
     termo *= -1 * x * x / ((i+1) * (i+2)); <cyan># compute potencia 2i de x e fatorial de 2i</cyan>
     i += 2;
  return soma;

<verm>def</verm> main () :
  tempo_inicial = time.time(); <cyan># "dispara o cronometro"...</cyan>
  <verd>print</verd>("    x | ineficiente | eficiente | math cos(x) | dist inef. | dist efic.");
  x = 0.0;
  for i in range(0, 10) :
    cosx = math.cos(x);
    auxcI = cossInef(x);
    auxcE = cossEfic(x);
    <verd>print</verd>(" %3.2f | %11.4f | %9.4f | %11.4f | %10.4f | %10.4f" %
         ( x, auxcI, auxcE, cosx, valor_absoluto(auxcI-cosx), valor_absoluto(auxcE-cosx) ));
    x += 0.05;

  tempo_final = time.time();
  <verd>print</verd>("Tempo em segundos: %f\n" % (tempo_final - tempo_inicial));

main();</pre></td></tr>
   </table></td></tr>
</table></center>
</p>

<p>
  Experimente rodar em sua máquina o código acima (completanto com o código da função <i>cossInef</i>, implementada na tab. 1).
  Na máquina usada em 2017 para o primeiro teste desse código, tanto rodando <i>C</i> quanto <i>Python</i>, produzem como resultado a tabela abaixo.
  Note que a medida
  que o <i>x</i> se afasta da origem, aparece mais erro, entretanto os erros são consistentemente maiores ao usar
  a implementação ingênua.

<center>
 <i>Tab. 4. As saídas geradas pelos códigos ineficientes e eficientes (da tabela 3) para aproximar <i>cosseno</i>.</i>
 <pre>    x | ineficiente | eficiente | math cos(x) | dist inef. | dist efic.
 0.00 |      1.0000 |    1.0000 |      1.0000 |     0.0000 |     0.0000
 0.05 |      1.0012 |    0.9988 |      0.9988 |     0.0025 |     0.0000
 0.10 |      1.0050 |    0.9950 |      0.9950 |     0.0100 |     0.0000
 0.15 |      1.0112 |    0.9888 |      0.9888 |     0.0225 |     0.0000
 0.20 |      1.0199 |    0.9801 |      0.9801 |     0.0399 |     0.0000
 0.25 |      1.0311 |    0.9689 |      0.9689 |     0.0622 |     0.0000
 0.30 |      1.0447 |    0.9553 |      0.9553 |     0.0893 |     0.0000
 0.35 |      1.0606 |    0.9394 |      0.9394 |     0.1213 |     0.0000
 0.40 |      1.0789 |    0.9211 |      0.9211 |     0.1579 |     0.0000
 0.45 |      1.0996 |    0.9004 |      0.9004 |     0.1991 |     0.0000</pre></center>
</p>

<p>
  Os resultados numéricos são os mesmos comparando o executável a partir do código <i>C</i> ou a interpretação do <i>Python</i>,
  Entretanto, os tempos de execução diferem,
  sendo significativamente menores utilizando a versão compilada (compilador <b>Gnu GCC</b>).
  Usando a mesma máquina (um PC com 2 processadores AMD Phenom II rodando Linux/Debian 8.8),
  os menores resultados de tempo de execução (dentre 100 testes) para o executável via <i>C</i> e o interpretado
  <i>Python</i>: <center><pre>
                   C          Python      
Tempo em segundos: 0.000079   0.000220</pre></center>
</p>

<p>
  Em novos testes, desta vez usando um computador de dois núcleos com processador <i>Intel Core i5-6400 CPU @ 2.70GHz</i>,
  com sistema <i>Debian GNU/Linux 9.12</i>, rodando 400 vezes, eliminando-se as linhas com comando de impressão
  (pois as saídas poderiam uniformizar os resultados por serem significativamente mais lentas),
  os resultados numéricos do executável (compilação <i>Gnu GCCC</i>) mostra um bastante superior ao interpretador <i>Python</i>.
  Os tempos médios das 400 rodadas, do menor tempo de execução e do maior tempo, para a versão compilada e interpretada foram
  (em segundos):
  <center><pre>
              C          Python
Tempo medio:  0.000520   0.008276
Tempo minimo: 0.000016   0.000076
Tempo maximo: 0.000945   0.016031</pre></center>
</p>

<!--
2020/08/13 - /proc/cpuinfo = 2 x Intel(R) Core(TM) i5-6400 CPU @ 2.70GHz
C
-->


<p>
Este é apenas um resumo para apresentar o assunto de eficiência de algoritmos, seu aprofundamente demanda muito mais tempo.  
Por exemplo, no IME-USP existe um curso (usualmente de segundo ano) cujo objeto de estudo é precisamente
discutir efeciência de algoritmos, o curso
<a href="http://uspdigital.usp.br/jupiterweb/obterDisciplina?sgldis=MAC0122&verdis=2"
   title="ver ementa">MAC0122 - Princípios de Desenvolvimento de Algoritmos</a>.
No programa de Verão do IME-USP temos o curso
<a href="http://www.ime.usp.br/verao/index.php/turmas/apresentacao.php"
   title="ver lista de cursos do ultimo Verao">Tópicos de Programação</a>.
</p>

  <p class="autoria">
    <a href="https://www.ime.usp.br/~leo" target="_blank" title="seguir para a pagina do prof. Leônidas">Leônidas de Oliveira Brandão</a><br/>
    <a href="http://www.ime.usp.br/~leo" target="_blank" title="seguir para a página do LInE">http://line.ime.usp.br</a>
  </p>

  <p class="rodape">
    <b>Alterações</b>:<br/>
    2020/08/15: novo formato, pequenas revisões<br/>
    2020/08/13: ampla revisão (introdução nova, com imagem), novo formato;<br/>
    2019/04/24: primeira versão
  </p>


</div>