Tiago Madeira

Básico

Análise de Algoritmos

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, maratonas e problemas em casa, é precisarmos medir o tempo que ele irá demorar.

Eu expliquei 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):

para i \leftarrow{} 1 até n, faça
 para j \leftarrow{} 1 até i, faça
     imprima i \times{} j \times{} n
 fim-para
fim-para

O que este algoritmo faz é, depois de receber a entrada \(n\) do usuário, imprimir o produto de \(n\) com todos dois números \(i\) e \(j\), tal que \(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 \(n + 1\) vezes.
  • Linha 2: Será executada \(n \times{} \sum_{i=1}^{n} + n\) vezes.
  • Linha 3: Será executada \(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 \(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 \(n\). Por isso, ele será executado \(n+1\) vezes, ao invés de simplesmente \(n\).

Linha 2

Este loop para será executado um número de vezes variável (\(i\)), que irá de \(1\) a \(n\). Portanto, ele será executado duas vezes (1 mais “o último condicional”) no primeiro loop de \(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 \(1\) a \(n\), mais \(n\) que são “os últimos condicionais”.

Linha 3

Exatamente o mesmo número que a Linha 2, mas sem “os últimos condicionais” (\(-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 \(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.

$$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:

\(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 \(n\) nele, neste caso, \(n^{2}\). Se tivéssemos \(2 n^{2}\), por exemplo, também usaríamos apenas \(n^{2}\) porque o \(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 pouco habituadas com matemática, essa parte é difícil e cansativa. 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.

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

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

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

Vou explicá-las, omitindo alguns fatos para tentar facilitar o entendimento, porque eu acho que analisar algoritmos é meio complicado e nessa parte é extremamente difícil ser didático. 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 \(\Theta{}\)

Lê-se “theta de gê de ene”.

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

A notação \(O\)

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

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

A notação \(\Omega{}\)

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

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

A notação \(o\)

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

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

A notação \(\omega{}\)

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

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

Para analisar problemas mais complexos como, por exemplo, recorrências, existem métodos bastante interessantes, como o Teorema Mestre que o Cormen apresenta no Capítulo 4. É uma boa leitura pra quem se interessou.


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.

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

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

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

$$c_{1}n^{2} \leq{} n^{2} + 3 n \leq{} c_{2} n^{2}$$

Se dividirmos tudo por \(n^{2}\), obteremos:

$$c_{1} \leq{} 1 + \frac{3}{n} \leq{} c_{2}$$

Agora separaremos as inequações.

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

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

Para satisfazer a Inequação 1, podemos quase automaticamente perceber que para qualquer \(n \geq{} 1\), é válido \(c_{1} = 1\) (ora, por mais que \(\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 \(n \geq{} 1\), é válido \(c_{2} = 4\) (a função só tende a diminuir a partir que \(n\) vai aumentando e com \(n=1\), \(c_{2}=4\)). Com isso, agora chegamos as três constantes que precisávamos.

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

Logo, concluímos que \(f(n) = n^{2} + 3n = \Theta{}(n^{2})\). Uma função que pertence a \(\Theta{}\), tem um limite assintótico superior e inferior e, portanto, pertenceria também a \(O(n^{2})\) e \(\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, é crucial sabermos analisar, mesmo que por cima, qual o algoritmo que é mais eficiente. Vou ficando por aqui…

Comentários

José Oliveira

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.

Tiago Madeira

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

RodrigoSol

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.

Regis

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!

Tiago Madeira » Análise de Algoritmos

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

André Macedo

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

John

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…

Tiago Madeira

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.

rafael

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.

claudio

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

Juliana

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?

Aline

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…

Jonathan

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…

Pitra

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

Jocel

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

Catiúscia

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!!

Dheyva Blanmy

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!

albert abel

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!

Dayane

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 .

Silvana

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

Evandro Madeira

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.

svjwbrxyz bnqtiruv

hsxcwrv mnxlhw pfgwc nedqmyo cskfqt vtzihdf ybdtaumqp

Pedro Petrício

Veleu cara, muito bom! Quem domina esse assunto, com certeza faz a diferença na programação…

Patrícia

Gostaria que alguem me ajudasse. Estou estudando Lógica de Programação em Visualg, e preciso resolver os seguintes exercícios: 1) Faça um algoritmo que leia um vetor de 10 posições do tipo real, que leia e calcule a soma destes números, como por exemplo 5+3=8, onde o resultado deve ser mostrado no final. 2) Desenvolver um vetor de 20 posições do tipo numérico, que verifique e mostre quais números são primos e faça a soma destes números. Pessoal me ajudem por favor! A todos os internautas o meu ABRAÇÃO! Patrícia

Francisco

Patrícia, olha se isso te ajuda… 1) algoritmo var v: vetor [1..10] de real Soma: real i: inteiro inicio para i de 1 ate 10 faca escreva (“Digite o”, i, “º número: “) leia (v[i]) Soma <- Soma + v[i] fimpara escreva (“Soma dos números: “, Soma) fimalgoritmo 2) algoritmo var v: vetor [1..20] de inteiro i, j, Resto, Total_Resto, Valor, Soma_Primos: inteiro inicio para i de 1 ate 20 faca escreva (“Digite o”, i, “º número: “) leia (Valor) Total_Resto <- 0 para j de 1 ate Valor faca Resto <- Valor % j se Resto = 0 entao Total_Resto <- Total_Resto + 1 fimse fimpara se Total_Resto = 2 entao v[i] <- Valor fimse fimpara escreva (“Primos :“) para i de 1 ate 20 faca se v[i] 0 entao escreva (v[i], “,”) Soma_Primos <- Soma_Primos + v[i] fimse se i = 20 entao escreval(“”) escreval (“Soma dos primos:“, Soma_Primos) fimse fimpara fimalgoritmo

Izidoro Storch

quero saber se na programação tem algum estilo padrão, tipo: variáveis: leia: para cada comando?tipo: para Enquanto etc.

eva

estou aprendendo algaritimo agora nunca vi isso,estou com mts duvidas gostaria que me enviase alguns exemplos. grata.

Guilherme Mariano

saudações sou angolanano e gostei das suas explicações e esclarecimento. estou a frequentando o curso de cinecia da computação em angola e tendo dificuldade na resolução de exercicios de analise de algoritmo e gostaria da sua ajuda. um abraço do tamanho de Angola

ULISSES PAIVA

GOSTARIA DE APRENDER OS COMANDOS DE ALGORITIMO ,QUANDO USÁ-LOS E O SIGNIFICADO DE CADA UM , TIPO: <- , ; , = , ( , / ,// ,# ,] E OUTROS MAIS QUE ESQUECI AGORA. OBRIGADO!

Laisa Alcantara Alianda

Olá Tiago!!! Sou aluna do curso CIÊNCIA DA COMPUTAÇÃO. Gostei mto da sua matéria!!! ficou bastante clara. aprendi coisas novas tbm. Podemos trocar conhecimentos!!??

Laisa Alcantara

Olá tiago!!! sou aluna do curso CIÊNCIA DO COMPUTAÇÃO; estive lendo sua matéria ficou ótima!!!

Jemerson Soares

Muito boa a explicação.Confesso que tive sérios problemas para entender esses conceitos, mas agora clareou. Abraços!

Rick

Muito bom artigo! Me ajudou muito. Obrigado.

fabio

Ola tiago estou começando agora sobre algoritimo,não estou conseguindo achar o foco do raciocinio tem como me dar alguma dica abraço!”

Welber

Será que alguém poderia me ajudar em uma dúvida? Não estou conseguindo desenvolver um algoritmo que permita a ordenação de um vetor de 20 posições, preenchido com números aleatórios entre 1 e 100, inclusive.

Alessandro

olá eu sou aluno do e-jovem, e tenho um exercicio que executado informará se o número digitado é primo ou não!!! por favor me ajude, eu já não sei mais o que fazer!!!

Jeronimo

I love you man!

Thiago Marinho

Bom artigo! ajudou-me

Werlem Martins

Bom dia! passoal, estou vendo que vcs! estão na dúvidas de questões de primeiro semestre, na verdade vcs não deveriam sair de sala com esta dúvida, pois saindo com ela os únicos prejudicados serão vcs, não saia da sala com dúvida pergunte!, pois o professor está lá pra isso, pra ensinar, algunhas alunos ficam constragidos em perguntar ao professor, com medo de passar como burro perante ao professor e ao colegas, o professor estalá pra isso se ele é inguinorante em responder as suas perguntas, responda a ele que está sendo pago pra isso, e aos colegas que zuarem , pode ficar trnaquilo não os responda, pois vc vai terminar o semesttre realmente preparado para assumir a vaga que está te esperando, e os otários que o zuaram também vão assumir um vaga no mercado, mas no mercado em frente a uma esquina, falando da vida alheia. abraÇos e um bom estudaos a todos!

Pedro D

Excelente artigo! Já agora acho que encontrei um pequeno erro no primeiro exemplo do Algoritmo 1), em que a linha 2 deveria de ser n+SUM_i=1_ate_n (i) e não n*SUM_i=1_ate_n (1) + n. Deixo aqui um codigo exemplo que demonstra o meu ponto de vista: http://ideone.com/qziSQ Abraço!

breno

preciso fazer um programa para preencher uma matriz 3x5, mostrar a soma de cada linha e mostrar qual linha tem o maior valor somado preciso de ajuda #include int main() { int mtrx [3][5]; int a, b; float Maior, soma=0; for (a=0; a<3; a++) { for(b=0; b<5; b++) { cout<> mtrx [a][b]; Maior = mtrx [0] [0]; soma=Maior; { Maior=mtrx [a][b]; } } } for (a=0; a<3; a++) { cout<<”\n”; for(b=0; b<5; b++) { cout<<mtrx [a][b]<<” “; } } for (a=0; a<3; a++) { for(b=0; b<5; b++) { cout<<”\n”; mtrx[a][b]=Maior; soma=a+b; } } cout<<”\n\t\tFim do Programa\n”; cout<<”\n A soma e:”<<soma; system(“PAUSE”); return 0; }

zenildoo

olha gostei muito da sua pagina e gostaria enviases alguns exercicio ja efeito para m poder compreender melhor. Eu sou estudante do curso Engenharia Informática e tenho como cadeira Analise Algoritmo.obrigado

Ana

Me ajudou muito. Muito obrigada!

Obrigado! Seu comentário foi enviado e será publicado quando for aprovado.

Infelizmente ocorreu um erro ao enviar seu comentário.