Algoritmo – Um noção sobre Custos

Cena do filme Rede Social

Hoje, vou falar um pouco sobre custos de execução dos algoritmos. A ideia é passar uma noção de como mensurar o custo de um algoritmo.

Vamos pegar o problema abaixo:

Some todos os números entre 1 e 100

A primeira abordagem para resolver o problema acima seria a implementação abaixo:

int total = 0;
for(int i = 1; i <= 100; i++ )
   total = total + i;

Obs: Graças ao Caio, conseguimos colocar código aqui no blog =)

Quanto custa para o computador executar o algoritmo acima ?

Imagine que para cada instrução executada o custo seja 1, por exemplo:

  • Criar a variável total com valor 0, custa 1
  • Criar a variável com valor 1, custa 1
  • Comparar com 100, custa 1
  • Somar total com i e atribuir a total, custa 1
  • Incrementar i, custa 1

Com isso, podemos dizer que a implementação acima tem custo 1 + 1 + 3 * 100 = 302. Porque:

  • 1 – Para criar a variável total
  • 1 – Para criar a variável i
  • 300 – Para cada loop do for temos um custo de 3 ( comparação, soma e incremento) e como são 100 loops teremos um custo de 300.

Agora vamos dificultar um pouco as coisas:

Some todos os números pares entre 1 e 100

Implementando:

int total = 0;
for(int i = 1; i <= 100; i++ )
   if ( i % 2 == 0 )
      total = total + i;

O custo do algoritmo algoritmo sobe para 502 agora, porque colocamos uma instrução aritmética ( i % 2 ) e uma de comparação ( i % 2 == 0 ), ou seja adicionamos 2 de custo para cada loop.

Melhorando…

Imagine que você está executando o algoritmo acima em um celular bem, mas bem velho e bem limitado, você precisa otimizar o algoritmo para somar os números pares. Depois de pensar muito você chegou nisso:

int total = 0;
for(int i = 2; i <= 100; i += 2 )
      total = total + i;

O custo do algoritmo acima é 1 + 1 + 3 * 50 = 152. Porque:

  • 1 – Para criar a variável total
  • 1 – Para criar a variável i
  • 150 – Reduzimos a quantidade de loops para 50, pois incrementamos de 2 em 2 a partir de 2 (papo de louco), mas o custo por loop ainda é 3, logo 3 * 50 = 150

Por quê entender custos?

Ao analisar a segunda implementação que tem custo 502, fica claro que o gargalo está no for e o jeito de melhorá-lo é diminuir o custo dos loops. Você só chega nessa conclusão entendo o custo de execução do algoritmo.

Gauss

Será que dá pra diminuir mais o custo ? 152 é o mínimo ?

Voltando para a oitava série, você deve se lembrar da história sobre Gauss ( todo professor de matemática conta, eu acho =P ).

Um dia na escola de Gauss ( que tinha 8 anos segundo a lenda ), a professora de matemática estava cansada para dar aula, então pediu para os alunos somarem os números de 1 a 100, isso iria ocupar um bom tempo deles. Para infelicidade da professora, em alguns minutos, Gauss aparece com a resposta, ele havia criado a fórmula da progressão aritmética.

Sn = (( a1 + an ) *  n ) / 2

Para conhecer mais: http://pt.wikipedia.org/wiki/Progressão_aritmética

Importância da matemática

Se implementarmos a fórmula de Gauss para os número de 1 a 100:

int total = ((1 + 100) * 100) / 2;

O custo é de 1 + 1 + 1 + 1 = 4. Porque:

  • 1 – Para a operação de soma
  • 1 – Para a operação de multiplicação
  • 1 – Para a operação de divisão
  • 1 – Criar a variável total e atribuir o valor

Agora implementando a fórmula para os números pares:

int total = ((2 + 100) * 50) / 2;

Veja que o custo continua mesmo. É a melhor solução para fazer a soma de um intervalo de números =) . Pois o custo não é sensível aos dados de entrada como nas 3 primeiras implementações, ou seja, se eu quiser somar um número de 1 a 1.000.000, ainda teria custo 4, já na implementação que utiliza o for o custo seria de 3.000.002.

A solução aritmética é sempre a melhor, por isso dê mais valor as aulas de matemática na escola e na faculdade.

O objetivo desse post é passar essa noção de custo e não explicar ao fundo como é mensurado o custo de um algoritmo, pois nem toda instrução tem custo 1, se quiser aprofundar no assunto indico o livro abaixo:

http://www.livrariasaraiva.com.br/produto/4061865

Para o dia a dia, o importante é ter uma noção, não precisa ser o expert em custos. Esse conhecimento é aplicado em outras áreas e não apenas programação, como em processos de produção ou até mesmo numa viagem de fim de semana.

Abraço!

Leia Mais