Ciência da Computação

Análise de Algoritmos

O objectivo da análise de algoritmos é o de prever o comportamento de um algoritmo, particularmente o seu tempo de execução em função do volume de dados de entrada, sem ter de implementar esse algoritmo. Dado que o comportamento de um algoritmo depende de diversos factores, é difícil prever o seu comportamento exacto. Em alternativa, procura-se extrair do algoritmo as suas características principais e basear a análise nessas características, ou seja, obtém-se uma análise aproximada e não uma descrição exacta do comportamento do algoritmo. Apesar de se recorrer a uma análise aproximada, já é possível obter informação suficiente sobre o algoritmo para o confrontar e comparar com outros algoritmos que resolvem o mesmo problema.

Um programador, colocado perante um problema de resolução computacional, tem de conceber um programa que permita encontrar soluções para esse problema. Uma abordagem à resolução do problema é dividi-lo em subproblemas, que por sua vez ainda podem ser subdivididos e, para cada um desses subproblemas, encontrar um algoritmo adequado que o resolva. Esse algoritmo pode ser idealizado pelo programador ou obtido a partir de livros ou de outras fontes, no caso de problemas que já tenham sido resolvidos por outros programadores. A questão que se coloca é como é que o programador pode saber se o algoritmo que concebeu ou encontrou (e pode encontrar vários) é ou não adequado às características particulares do seu problema. Por exemplo, se o programador pretender resolver um problema que implique uma ordenação de elementos de um conjunto, encontrará vários algoritmos de ordenação, dado que este é um problema conhecido. Então, como é que o programador sabe qual o algoritmo a escolher? Escolhe um aleatoriamente? Escolhe o que tiver menos linhas? Ou aquele que lhe parecer menos complexo? Obviamente que a resposta não pode ser assim tão simples. Normalmente, quando se procuram algoritmos, é fornecida para cada um, uma medida da