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!

Celso Wo

Apreciador de inovação em tecnologia nas mais diversas plataformas. Possui grande conhecimento em várias linguagens de desenvolvimento, entre elas Java, C, Objective C, PHP, Lua, Python e Ruby. Procura sempre focar em inovações nas áreas de inteligência artificial, redes neurais, aprendizagem de máquina e usabilidade.

Deixe uma resposta

O seu endereço de email não será publicado Campos obrigatórios são marcados *

Você pode usar estas tags e atributos de HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>