Análise de Algoritmos
Sunday, January 8th, 2006Analisar 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):
1. para i1 até n, faça 2. para j
j
O que este algoritmo faz é, depois de receber a entrada 
do usuário, imprimir o produto de com todos dois números 
e 
, tal que 
.
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
vezes. - Linha 2: Será executada
vezes. - Linha 3: Será executada
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 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 . Por isso, ele será executado 
vezes, ao invés de simplesmente .
Linha 2
Este loop para será executado um número de vezes variável (), que irá de 
a . Portanto, ele será executado duas vezes (1 mais "o último condicional") no primeiro loop de , 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 a , mais que são "os últimos condicionais".
Linha 3
Exatamente o mesmo número que a Linha 2, mas sem "os últimos condicionais" (
).
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 . 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.
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:
, 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 nele, neste caso, 
. Se tivéssemos 
, por exemplo, também usaríamos apenas porque o 
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:
Embora essas notações sejam conjuntos, usamos o sinal de igualdade (
) para expressar que 
pertence a algum deles, ao invés de usar o sinal de pertinência (
).
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 
Lê-se "theta de gê de ene".
, se existem constantes positivas 
, 
e 
tais que 
para todo 
.
A notação 
Lê-se "ó maiúsculo de gê de ene". Para quando há apenas um limite assintótico superior.
, se existem constantes positivas 
e tais que 
para todo .
A notação 
Lê-se "omega maiúsculo de gê de ene". Para quando há apenas um limite assintótico inferior.
, se existem constantes positivas e tais que 
para todo .
A notação 
Lê-se "ó minúsculo de gê de ene". Para quando há apenas um limite assintótico superior, sem permitir que 
. Utiliza-se a notação para denotar um limite superior que não é assintoticamente restrito.
, se para qualquer constante 
, existe uma constante 
tal que para todo .
A notação 
Lê-se "omega minúsculo de gê de ene". Para quando há apenas um limite assintótico inferior, sem permitir que 
. Utiliza-se a notação para denotar um limite inferior que não é assintoticamente restrito.
, se para qualquer constante , existe uma constante tal que para todo .
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... .
Vamos ver em que notação ele pode se encaixar, sabendo que 
seria a ordem de crescimento (parte importante) do nosso custo; no caso, .
Testamos primeiro se ele encaixa na função 
. Vamos substituir e (naquela função ali em cima, onde diz A notação ) pelos valores que conhecemos.
Se dividirmos tudo por , obteremos:
Agora separaremos as inequações.
Inequação 1: 
Inequação 2: 
Para satisfazer a Inequação 1, podemos quase automaticamente perceber que para qualquer 
, é válido 
(ora, por mais que 
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 , é válido 
(a função só tende a diminuir a partir que vai aumentando e com 
, 
). Com isso, agora chegamos as três constantes que precisávamos.
(o menor valor de ) 
; ; .
Logo, concluímos que 
. Uma função que pertence a , tem um limite assintótico superior e inferior e, portanto, pertenceria também a 
e 
, 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...