Algoritmos I (página 2)

O algoritmo, portanto, é a lógica do nosso problema matemático, ou, informático. É a seqüência de passos que eu faço na minha cabeça (ou, quando é complexo, no papel) antes de escrever, em C, a função f:

}

Se formos pensar, veremos que tudo o que fazemos é um algoritmo, é um procedimento que recebe uma entrada e envia uma saída. Não só no computador, mas na vida. Quando eu falo com alguém, eu espero sua entrada (o que a pessoa fala pra mim), então penso e transformo essa entrada numa saída (a resposta que vou dar pra pessoa). E assim é com várias outras coisas. Podemos dizer também que acordar é um algoritmo, por exemplo:

Podem existir vários algoritmos diferentes para resolver o mesmo problema. No caso de Acordar, cada um acorda de forma diferente, por exemplo. Foi até um exemplo meio estranho esse aí, mas outro algoritmo poderia dar outra saída, como por exemplo simplesmente abrir os olhos e cair da cama. Ou no caso acima da função matemática, poderíamos ter um algoritmo que fizesse a mesma coisa de maneira diferente também.

O algoritmo que usamos depende principalmente do tempo que ele demora pra ser executado e a memória que ele gasta no computador. Chamamos isso de custo. Quando começarmos a ver os algoritmos de ordenação de vetores, veremos que cada algoritmo faz uma coisa diferente, mas todos fazem a mesma coisa: ordenar o vetor. Para uma entrada pequena, um pode ser mais rápido... Para uma maior, outro. Portanto, o algoritmo que queremos usar (o tempo que ele vai demorar pra ser executado e a memória que ele vai gastar no computador) depende principalmente do tamanho da entrada (que chamamos de N e no exemplo da função seria a variável X).

Na maioria dos casos (e vai ser sempre assim aqui nos meus artigos), a entrada será o teclado (por exemplo, o usuário digita o X para a função) e a saída será a tela (por exemplo, o programa imprime o resultado da função, o Y, para a tela). Essas são a entrada e saída padrão (standard input output do C), que é usada nas olimpíadas e na maioria dos problemas que resolvemos no computador.

Em resumo, portanto, um algoritmo é a lógica de um programa computacional. Nos próximos artigos, isso deverá ser mais esclarecido e começaremos a ver algoritmos "de verdade"

Qualquer dúvida, sugestão ou notificação de erro; poste um comentário ou me envie um e-ma

para j 2 até comprimento do vetor, faça

elemento vetor[j]

i j - 1

enquanto i > 0 e vetor[i] > elemento, faça

vetor[i + 1] vetor[i]

i i - 1

fim-enquanto

vetor[i + 1] elemento

Se você programa em qualquer linguagem, você não terá dificuldade em traduzir esse pseudocódigo para ela. O pseudocódigo é sempre uma maneira bem simples de escrever o código. Veja por exemplo, o mesmo código em C:

}

Você deve ter percebido que ao invés de usar três linhas com uma declaração, um condicional e um incremento, eu juntei todos num só for. Mas por isso o algoritmo é bem simples e sempre parte do princípio de que a sua linguagem é simples. Veja só a implementação do código em Pascal e compare-a com a do pseudocódigo:

Linha por linha ela é exatamente igual! A única diferença é que o pseudocódigo é traduzido... Geralmente os pseudocódigos são parecidos sempre com essa base e suas implementações não são muito diferentes. E vai ser sempre dessa maneira que eu vou representar os algoritmos (usando pseudocódigos e alguns traduzindo para C para mostrar implementações)

Quando entrarmos no assunto de ordenação de vetores, analisaremos esse algoritmo do Insertion Sort e outros, mas por enquanto vamos ficando por aqui.

Este artigo é o terceiro da série sobre algoritmos. Se você ainda não leu os artigos anteriores, sugiro que leia antes de continuar:

Acredito que você que já leu os dois primeiros artigos já deve saber, mas não custa lembrar: algoritmo é a relação entre entrada e saída do programa, é o rascunho do programa, o projeto. E um projeto antes de colocar a mão na massa é indispensável. Enquanto a implementação é a função dos pedreiros, o algoritmo é a função dos engenheiros. Se os engenheiros não existissem, acho que os pedreiros não iam conseguir fazer as casas e os prédios que eles constroem hoje em dia!

O algoritmo sempre existe, mesmo que apenas no seu pensamento. A primeira coisa que você pensa quando quer fazer uma aplicação (a não ser que você seja louco) é: o que é a aplicação? O que ela vai fazer? E se você sair implementando uma coisa complexa, você vai se decepcionar depois demorando mais do que o tempo de fazer a implementação só para limpar o código! Por isso, representar algoritmos complexos é essencial.

E mais... Mesmo se você tivesse tempo infinito, memória infinita, etc. e tal (não tivesse necessidade de limpar o código), você vai precisar de um algoritmo pra provar que o seu programa funciona, para se organizar e para estudar a sua lógica. Se você não planejar um algoritmo para o caso acima, qualquer funcionalidade que você queira adicionar no meio, por falta de projeto e organização, vai demorar bem mais tempo. Por isso, algoritmo não é uma perda de tempo antes da programação, mas a programação é que se torna uma perda de tempo quando não teve um algoritmo (ou, um projeto). O livro Algoritmos: Teoria e Prática reforça essa interessante idéia na página 7:

Suponha que os computadores fossem infinitamente rápidos e que a memória do computador fosse livre. Você teria alguma razão para estudar algoritmos? A resposta é sim, se não por outra razão, pelo menos porque você ainda gostaria de demonstrar que o método da sua solução termina, e o faz com a resposta certa.

Outra utilidade do algoritmo é compartilhar idéias de problemas complexos. Todo programador entende um pseudocódigo e por isso convém muitas vezes apresentar sua idéia de um programa em forma de um algoritmo, num pseudocódigo, ao invés de passar um programa implementado em C para uma dúzia de programadores de VBScript.

Existe uma série de algoritmos comuns que todo programador deve conhecer (projetos prontos para muitas coisas complicadas que precisamos implementar no dia-a-dia) e isso é o que vamos começar a estudar no próximo artigo.

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 1 até n, faça

2. para j 1 até i, faça

3. imprima i j n

4. fim-para

5. fim-para

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.

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).

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 .

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".

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.

Simplificando esta operação, teremos:

, uma função quadrática.

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.

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:

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 é 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].

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

, se existem constantes positivas , e tais que para todo .

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 .

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 .

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 .

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 .

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

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, é importante sabermos analisar, mesmo que por cima, qual o algoritmo que é mais eficiente.