Algoritmos Computacionais

Artigos sobre lógica de programação por Tiago Madeira

algoritmo: do Lat. algorithmos < Ár. alkharizmi: [Inform.] conjunto de etapas bem definidas necessárias para chegar à resolução de um problema.

« Qual a utilidade do algoritmo?
Recursão »

Análise de Algoritmos

January 8, 2006

Este artigo é o quarto da Série Algoritmos. Se você ainda não leu os artigos anteriores, sugiro que leia antes de continuar:

Analisar um algoritmo é prever o que o algoritmo irá precisar. Às vezes o hardware é importante, mas acho que o que acontece com mais freqüência, ao menos em olimpíadas e problemas em casa, é precisarmos medir o tempo que ele irá demorar.

Eu explanei em algum dos artigos anteriores que o tempo de um algoritmo depende geralmente do tamanho de sua entrada. Com este artigo, pretendo explicar como analisamos um algoritmo baseado nesse tamanho de sua entrada para compará-lo com outros algoritmos e ter uma noção de quanto tempo ele vai demorar.

Para o entendimento ficar mais fácil, vamos partir do seguinte algoritmo (que vamos chamar de Algoritmo 1):

1. para i LaTeX: leftarrow{} 1 até n, faça
2.	para j LaTeX: leftarrow{} 1 até i, faça
3.		imprima i LaTeX: times{} j LaTeX: times{} n
4.	fim-para
5. fim-para

O que este algoritmo faz é, depois de receber a entrada LaTeX: n do usuário, imprimir o produto de LaTeX: n com todos dois números LaTeX: i e LaTeX: j, tal que LaTeX: j \leq{} i \leq{} n.

Para medir o custo do algoritmo, nossa análise consistirá em ver quantas vezes cada passo é executado. Mediremos o custo de cada linha (cada passo a ser executado), sempre em função de n, que para este algoritmo é a variável mais importante (aliás, a única variável). Por isso o pseudocódigo do Algoritmo 1 está com suas linhas numeradas. Vamos analisar...

  • Linha 1: Será executada LaTeX: n + 1 vezes.
  • Linha 2: Será executada LaTeX: n \times{} \sum_{i=1}^{n} + n vezes.
  • Linha 3: Será executada LaTeX: n \times{} \sum_{i=1}^{n} vezes.
  • Linhas 4 e 5: Não tem custo. :)

Por que estes números de execução?

Se você já entendeu por que cada passo é executado este número de vezes, pode pular essa parte (continuar a ler a partir da linha horizontal).

Linha 1

O loop para voltará para si mesmo LaTeX: n vezes, isso é, testará novamente sua condicional e incrementará um. Por sempre testar um condicional, no final ele terá que testar novamente para dizer que já passou de LaTeX: n. Por isso, ele será executado LaTeX: n+1 vezes, ao invés de simplesmente LaTeX: n.

Linha 2

Este loop para será executado um número de vezes variável (LaTeX: i), que irá de LaTeX: 1 a LaTeX: n. Portanto, ele será executado duas vezes (1 mais "o último condicional") no primeiro loop de LaTeX: i, três (2 mais "o último condicional") no segundo, e por aí vai. Com isso, ele será executado o número de vezes que equivale a soma de LaTeX: 1 a LaTeX: n, mais LaTeX: n que são "os últimos condicionais".

Linha 3

Exatamente o mesmo número que a Linha 2, mas sem "os últimos condicionais" (LaTeX: -n).

Imprimir algo na tela pode demorar mais do que fazer uma operação, mas a análise de algoritmos é uma coisa bem rústica. Desprezamos todas as constantes, com isso só levando a sério a informação importante: neste caso, apenas LaTeX: n. Então agora, vamos escrever o tempo de execução do algoritmo, que é a soma dos tempos de execução para cada instrução executada.

LaTeX: T(n) = (n + 1) + (\sum_{i=1}^{n} + n) + (\sum_{i=1}^{n})

Os parênteses não são necessários, mas coloquei para ajudar na visualização separando o custo de cada instrução.

Simplificando esta operação, teremos:

LaTeX: T(n) = n^{2} + 3n, uma função quadrática.

Ordem de Crescimento

Como eu já disse antes, descobrir o custo de um algoritmo é uma coisa feita sem precisão, porque para entradas realmente grandes (que são casos onde precisamos do computador!) as constantes não importam. Agora vamos determinar a ordem de crescimento de um algoritmo resgatando do nosso algoritmo apenas o valor mais importante, o maior expoente de LaTeX: n nele, neste caso, LaTeX: n^{2}. Se tivéssemos LaTeX: 2 n^{2}, por exemplo, também usaríamos apenas LaTeX: n^{2} porque o LaTeX: 2 que multiplica também é desprezível!

Vamos agora aprender como representar o custo desse algoritmo usando notações assintóticas com a ordem de crescimento do algoritmo.

Se você não entendeu alguma coisa aí em cima, sugiro reler antes de continuar...

Notações Assintóticas

Sugestão

Principalmente para pessoas mais novas, esta parte é cansativa porque exige bastante conhecimento de matemática. Quando eu comecei a aprender isto, talvez por causa da matemática tão básica que é ensinada na escola, eu não entendia nada... Mas só quero dar uma dica: se você não entender direito ou achar muito complicado, pule para a próxima linha horizontal ao invés de desistir e dizer que "algoritmos são muito difíceis". Tentei fazer o artigo para você poder pular essa parte e mesmo assim não parar no estudo dos algoritmos... Depois, com o tempo, você vai aprendendo isso (peça pro seu professor de matemática dar uma ajuda).

As notações que usamos para descrever o tempo de execução de um algoritmo são cinco:

  • LaTeX: \Theta{}
  • LaTeX: O
  • LaTeX: \Omega{}
  • LaTeX: o
  • LaTeX: \omega{}

Embora essas notações sejam conjuntos, usamos o sinal de igualdade (LaTeX: =) para expressar que LaTeX: f(n) pertence a algum deles, ao invés de usar o sinal de pertinência (LaTeX: \in{}).

Vou explicá-las, omitindo alguns fatos para tentar facilitar o entendimento, porque eu acho que analisar algoritmos é meio complicado. E nessa parte é meio difícil pôr didática. Mas se você realmente se interessar, você pode me enviar um comentário pedindo mais um artigo sobre isso (e eu terei o prazer de até pesquisar para informar-lhes mais) ou então leia o Capítulo 3 do livro Algoritmos: Teoria e Prática, que acredito que seja bem completo. Gostaria de enfatizar aqui que meu objetivo com essa série é tornar uma introdução a algoritmos simples e não ser uma referência, como é o objetivo, por exemplo, do livro do Cormen [et al].

A notação LaTeX: \Theta{}

Lê-se "theta de gê de ene".

LaTeX: \Theta{}(g(n)) = f(n), se existem constantes positivas LaTeX: c_{1}, LaTeX: c_{2} e LaTeX: n_{0} tais que LaTeX: 0 \leq{} c_{1} g(n) \leq{} f(n) \leq{} c_{2} g(n) para todo LaTeX: n \geq{} n_{0}.

A notação LaTeX: O

Lê-se "ó maiúsculo de gê de ene". Para quando há apenas um limite assintótico superior.

LaTeX: O(g(n)) = f(n), se existem constantes positivas LaTeX: c e LaTeX: n_{0} tais que LaTeX: 0 \leq{} f(n) \leq{} cg(n) para todo LaTeX: n \geq{} n_{0}.

A notação LaTeX: \Omega{}

Lê-se "omega maiúsculo de gê de ene". Para quando há apenas um limite assintótico inferior.

LaTeX: \Omega{}(g(n)) = f(n), se existem constantes positivas LaTeX: c e LaTeX: n_{0} tais que LaTeX: 0 \leq{} cg(n) \leq{} f(n) para todo LaTeX: n \geq{} n_{0}.

A notação LaTeX: o

Lê-se "ó minúsculo de gê de ene". Para quando há apenas um limite assintótico superior, sem permitir que LaTeX: f(n) = cg(n). Utiliza-se a notação LaTeX: o para denotar um limite superior que não é assintoticamente restrito.

LaTeX: o(g(n)) = f(n), se para qualquer constante LaTeX: c > 0, existe uma constante LaTeX: n_{0} > 0 tal que LaTeX: 0 \leq{} f(n) \leq{} cg(n) para todo LaTeX: n \geq{} n_{0}.

A notação LaTeX: \omega{}

Lê-se "omega minúsculo de gê de ene". Para quando há apenas um limite assintótico inferior, sem permitir que LaTeX: cg(n) = f(n). Utiliza-se a notação LaTeX: \omega{} para denotar um limite inferior que não é assintoticamente restrito.

LaTeX: \omega{}(g(n)) = f(n), se para qualquer constante LaTeX: c > 0, existe uma constante LaTeX: n_{0} > 0 tal que LaTeX: 0 \leq{} cg(n) \leq{} f(n) para todo LaTeX: n \geq{} n_{0}.

Podemos criar várias comparações entre estas funções, mas isto não vem ao caso. O importante é saber em que notação a nossa função se encontra. Com o tempo vamos compreendendo melhor essas fórmulas (se você está boiando, não se assuste, eu também tive muita dificuldade com isso no começo).

Vamos relembrar o custo de nosso algoritmo... LaTeX: T(n) = n^{2} + 3n.

Vamos ver em que notação ele pode se encaixar, sabendo que LaTeX: g(n) seria a ordem de crescimento (parte importante) do nosso custo; no caso, LaTeX: n^{2}.

Testamos primeiro se ele encaixa na função LaTeX: \Theta{}(n^{2}). Vamos substituir LaTeX: f(n) e LaTeX: g(n) (naquela função ali em cima, onde diz A notação LaTeX: \Theta{}) pelos valores que conhecemos.

LaTeX: c_{1}n^{2} \leq{} n^{2} + 3 n \leq{} c_{2} n^{2}

Se dividirmos tudo por LaTeX: n^{2}, obteremos:

LaTeX: c_{1} \leq{} 1 + \frac{3}{n} \leq{} c_{2}

Agora separaremos as inequações.

Inequação 1: LaTeX: c_{1} \leq{} 1 + \frac{3}{n}

Inequação 2: LaTeX: 1 + \frac{3}{n} \leq{} c_{2}

Para satisfazer a Inequação 1, podemos quase automaticamente perceber que para qualquer LaTeX: n \geq{} 1, é válido LaTeX: c_{1} = 1 (ora, por mais que LaTeX: \frac{3}{n} chegue perto de 0, sempre ainda vamos ter a constante 1 adicionada a ele). Para satisfazer a Inequação 2, podemos perceber facilmente que para qualquer LaTeX: n \geq{} 1, é válido LaTeX: c_{2} = 4 (a função só tende a diminuir a partir que LaTeX: n vai aumentando e com LaTeX: n=1, LaTeX: c_{2}=4). Com isso, agora chegamos as três constantes que precisávamos.

LaTeX: n_{0} (o menor valor de LaTeX: n) LaTeX: = 1; LaTeX: c_{1} = 1; LaTeX: c_{2} = 4.

Logo, concluímos que LaTeX: f(n) = n^{2} + 3n = \Theta{}(n^{2}). Uma função que pertence a LaTeX: \Theta{}, tem um limite assintótico superior e inferior e, portanto, pertenceria também a LaTeX: O(n^{2}) e LaTeX: \Omega{}(n^{2}), mas nem é necessário testar os outros valores porque já identificamos nossa função como "theta de ene ao quadrado", que é a função mais "retinha" que podemos esperar.

Bom... Nos próximos artigos, veremos que um mesmo problema pode ter várias soluções diferentes com custos ainda mais diferentes! Por isso, é importante sabermos analisar, mesmo que por cima, qual o algoritmo que é mais eficiente.

Espero que tenham gostado do artigo. Qualquer dúvida, sugestão ou notificação de erro; poste um comentário ou me envie um e-mail.

Compare Preços de: notebooks, acer aspire, hp pavilion, computadores, pentium 4, nintendo wii, ps3, celulares, câmeras digitais

Categoria(s): Básico

23 comentários

#1 | Tiago Madeira (08/01/2006)

Ficou um artigo muito chato ou complicado? Acho que a falta de comentários só pode ser por causa disso ou porque esse assunto não é novidade pra ninguém! :( Mas se alguém tiver dúvida, comente aí, eu terei um prazer enorme em ver que você pelo menos leu o artigo! Hehehe… :)

#2 | José Oliveira (08/01/2006)

Ficou ótimo…. para alunos de ciência da computação! :D

Só pra adicionar: a análise de um algorítmo é pra medir o custo dele.

#3 | Tiago Madeira (08/01/2006)

Valeu pelo comentário, Zé! Vou tentar maneirar no próximo artigo falando sobre recursão… ;)

#4 | RodrigoSol (13/01/2006)

Fala Tiago,

Análise de ordem de complexidade de algoritmos é uma coisa mais acadêmica e normalmente os caras que estão no mercado não lembram dessas coisas. Então não esquente pelo Ibope por que ficou legal.

#5 | Tiago Madeira (14/01/2006)

Valeu pelo comentário, Rodrigo! :)

#6 | Regis (19/06/2006)

Olá Tiago. Sou aluno de mestrado em computação e ainda não fiz a disciplina obrigatória de Análise de Algoritmos. Como não tive esse curso na graduação, achei o assunto bem complicado e que se não tiver uma boa base matemática (esse é o meu caso), vai sofrer como um cão.
Para tentar aliviar o trauma quando começar a cursar a disciplina, gostaria de ir lendo artigos e livro sobre o assunto. Vc tem mais alguma indicação de livros para oferecer? Se possível, livros usados em cursos de graduação.
Valeu!

#7 | Tiago Madeira » Análise de Algoritmos (10/12/2006)

[…] O artigo está em outro local agora: Análise de Algoritmos […]

#8 | André Macedo (08/03/2007)

Gostaria de saber se alguém daqui poderia me ajudar a resolver os seguintes algoritmos:

1. Os trechos do algoritmo abaixo implementam estruturas de repetição. Responda quantas vezes as instruções (dentro da estrutura de repetição) serão executadas em cada trecho?

a) contador = 0
enquanto contador

#9 | John (16/04/2007)

Faltou dizer que você copiou boa parte desse texto do livro
do Cormen: Introduction to Algorithms… Pelo menos cita
o autor, né… se não fica um plágio e tanto…

#10 | Tiago Madeira (16/04/2007)

Não tem nenhum texto copiado, exceto as definições das notações, e isso está explícito no início do título Ordem de Crescimento. Além disso eu sempre enfatizo que isso aqui não é uma referência e sempre sugiro que quem se interessar mais leia o livro do Cormen. Uma busca por “Cormen” nesse site pode lhe mostrar várias vezes eu citando este livro como referência.

#11 | rafael (03/05/2007)

Olá, eu passei no curso de ciênc da computação da UFPE, mas optei por 2ª entrada. Enquanto as aulas ñ começam eu resolvi tentar aprender a programar. Comecei a ler teus artigos e tava entendendo, mas esse ñ entendi muita coisa, ta um pouco complicado( é q eu ainda sou um leigo). Se vc pudesse explicar melhor os algoritmos, dizendo o q significa cada sinal, eu agradeceria.

#12 | claudio (10/05/2007)

por favor alguem pode me responder o que faz um algoritmo ser melhor que o outro?
e quais os criterios que são utilizados para avaliar a qualidade de um algoritmo?

claudio

#13 | Juliana (13/05/2007)

por favor alguem pode me responder o que faz um algoritmo ser melhor que o outro?
e quais os criterios que são utilizados para avaliar a qualidade de um algoritmo?

#14 | Aline (14/05/2007)

Acho que tem uma galera ai pesquisando o mesmo que eu, precisamos que alguém explique o que faz um algoritmo ser melhor que o outro?
e quais os criterios que são utilizados para avaliar a qualidade de um algoritmo?

Tiago, show de bola ein…parabéns, adorei…estou entendo muitas coisas que ficaram vagas nas aulas…

#15 | Jonathan (07/06/2007)

Bom tiago eu não terminei de ler o artigo, mas acho que entre esse e o artigo anterior faltaram alguns pingos nos is, é um passo enorme pra quem esta aprendendo a base dos algoritmos passar a analizar o desempenho deles, mesmo pra quem já conhece o esqueleto das linguagem…

#16 | Pitra (25/07/2007)

Iniciei um curso de informatica necessito a vossa ajuda de uma forma mais simple para conhecer as regras na constituicao de um algoritmo.
Seja a minha estrutura basic de VisuAlg 2.0:
algoritmo “semnome”
// Função :
// Autor :
// Data : 7/25/2007
// Seção de Declarações
var
inicio
// Seção de Comandos
fimalgoritmo

Podes dizer como comecar?

Obrigado

#17 | Jocel (14/08/2007)

Não encontrei nada sobre Busca (Searching)
procuro algoritmo otimo (perfeito) e definição do problema (entender o problema), e preciso achar o algoritmo mais adequado relacionando velocidade e eficiencia, mas não encontro nada sobre busca
Se puder me ajudar, obrigado

#18 | Catiúscia (11/01/2008)

Olá Tiago….
Tudo bom???
Bem, sou aluna do curso Redes em Computadores.
Esse ano iniciarei o Segundo ano..
Estava até indo bem até aparecer os Algoritmos..
Li seu tutorial e parece q quanto mais busco informações menos entendo…
Gostaria que se fosse possível vc estar me ajudando de uma forma simples e com bastante exercícios…
Queria muito começar esse meu segundo ano de faculdade tendo uma noção melhor sobre algoritmos..
Seria possível uma ajuda???
Desde já agradeço…
Um abraço!!

#19 | Dheyva Blanmy (21/01/2008)

Seguinte, acabei de passar na UFAC…
Fiz Sistemas de Informação, só começo a estudar em abril, mas andei dando uma olhadinha por aqui e gostei, deu até pra entender algumas coisas…
Parabéns! De agora em diante sempre vou dar uma passada por aqui…

Beijos!

#20 | albert abel (05/02/2008)

tiago seus artigos são maravilhosos
fiquei mt contente de poder tirar minhas dúvidas com eles…
sua análise de algoritmos está excepcional
see ya!

#21 | Dayane (19/02/2008)

ola meu nome e Dayane , eu iniciei
sistemas de informacao esse ano ,
da parte 1 a parte tres que inclusive
fiquei boiando ! Bom estou no primeiro
semestre , mas ja estou adiantando o que
vou ver nas aulas .
Gostei dos seus artigos , sao bastante claros .

bjoo , obrigada .

#22 | Silvana (08/03/2008)

Olá Tiago, gostei muito da página. Estou no primeiro semestre de Tecnologia em análise e desenvolvimento de sistemas, não tive uma boa base em matemática gostaria de saber mais sobre regras dos algoritmos e o que posso estudar?

obrigada

#23 | Evandro Madeira (29/04/2008)

Faço o curso de Ciência da Computação e estou na segunda fase, lógo na primeira fase ja tive a disciplina de Algoritmo, me dei mau, foi a única disciplina que rodei.
Os três primeiros artios eu li e entendi na boa, agora esse quarto quando começou a complicar eu me perdi todo. Mas os artigos estão todos ótimos, eu é que tenho que estudar mais.

Parabéns Tiago MADEIRA, ótimo trabalho.

Escreva um comentário

Dados pessoais

Seu e-mail não será publicado, mas você deve informá-lo para o autor poder responder seu comentário.

HTML 4.01 Strict: Você pode usar as seguintes tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Artigos relacionados:

53 assinantes

Mais artigos

Comentários recentes

  • Matheus Eduardo Maura: Faço engenharia eletrica-eletronica( UNIRP SÃO JOSE DO RIO PRETO), e...
  • rafael: muito legal o artigo mas teria como resolver esse algoritmo nao consegui de jeito nenhum,...
  • Roger: Bom artigo. Podia atualizar esse site
  • Aline Celestrino Bento: o que É ALGORITMO=exemplo:35 :7 porque eu ñ sei ALINE
  • Claudio: eu gostaria de saber este algoritmo: faça um algoritmo que determine, para um digrafo,...
  • ingrid morgana gomes paes: que bacana que legau isso e emtesamte e legau para apremder mais a...
  • Filipe Névola: filipe.bico@hotmail. com
  • Filipe Névola: Boa noite, gostaria de saber se você tem alguma implementação de menor caminho...
  • Carlos Luiz Silva Meirelles: estou fazendo curso de informática gratuito patrocindo pelo estado....
  • Maria Regina de Queiroz: Olá Tiago, li os seus artigos e gostei muito, gostaria se possivel que...

Categorias

Escrevo também...

  • Tiago Madeira
    Site pessoal e blog do autor destes artigos
  • Mal Vicioso
    Blog sobre filosofia e sobre a hipocrisia da sociedade

Links

Sobre o design

Este design foi copiado do CSS Zen Garden e modificado com autorização de seu autor, Gunta Klavina.

Licença

Todo o conteúdo deste site (incluindo textos, imagens, arquivos de áudio e quaisquer outros trabalhos), exceto quando especificado o contrário, está licenciado por Tiago Madeira sob uma Licença Creative Commons.

HTML 4.01 gerado por WordPress em 0.618 segundos.