Introdução à análise de algoritmos

Os algoritmos fazem parte do dia a dia das pessoas. Seja uma receita culinária ou instruções para uso de medicamentos. Ou seja, é uma sequência de ações executáveis para chegar à solução de um determinado tipo de problema. Segundo Edsger Dijkstra, um algoritmo corresponde a uma descrição de um padrão de comportamento, expresso em termos de um conjunto finito de ações.

Desta forma, a análise de algoritmos (descrita e difundida por D.E. Knuth) tem como função determinar os recursos necessários para executar um dado algoritmo. Ela estuda a correção e o desempenho através da análise de correção e da análise de complexidade. Dados dois algoritmos para um mesmo problema, a análise permite decidir qual dos dois é mais eficiente.

Curso C Básico

Conhecer o curso

Análise da correção

A análise da correção procura entender porque um dado algoritmo funciona. É preciso ter certeza de que o algoritmo está correto. Como algoritmos prometem resolver problemas, é esperado que ele cumpra essa premissa.

Análise da complexidade

A Análise da complexidade procura estimar a velocidade do algoritmo. Prever o tempo que o algoritmo vai consumir. Verificar qual é o custo de usar um dado algoritmo para resolver um problema específico. Porém, neste aspecto, encontram-se duas dificuldades:

1. O tempo gasto depende dos dados de entrada.
2. O tempo também depende da capacidade de hardware do computador utilizado.

Mas, mesmo assim, é possível definir a complexidade de determinado algoritmo.

Para medir o custo de execução de um algoritmo é comum definir uma função de custo ou função de complexidade, f; f(n) é a medida do tempo necessário para executar um algoritmo para um problema de tamanho n;

Para entendermos melhor, vejamos o trecho de código abaixo:

int soma = 0;
for (i=0; i<n; i++)
    soma = soma + vet[i];

O custo para execução deste algoritmo é f(n) = n. Pois o laço executa de acordo com o tamanho de n. Se n=10, logo o laço executará 10 vezes, se for igual a 100 executará 100 vezes.

Podemos tornar este algoritmo mais eficiente fazendo a seguinte modificação:

int soma = vet[0]; 
for (i=1; i<n; i++)
    soma = soma + vet[i];

Assim, temos uma nova função de complexidade, f(n) = n - 1.

Os dois trechos de códigos resolvem o mesmo problema, somar os elementos de um vetor. Porém, cada um tem um custo de execução diferente do outro, a partir da análise, podemos definir qual é o algoritmo mais eficiente para resolver este problema específico.

Melhor caso, Pior caso, Caso Médio.

Na análise da complexidade, definimos para um algoritmo, o melhor, o pior e o caso médio, como forma de mensurar o custo do algoritmo de resolver determinado problema diante de diferentes entradas.

• Melhor caso: é quando o algoritmo representa o menor tempo de execução sobre todas as entradas de tamanho n;

• Pior caso: maior tempo de execução sobre todas as entradas de tamanho n;

• Caso médio (ou caso esperado): é a média dos tempos de execução de todas as entradas de tamanho n.

Desta forma, considere o problema de acessar um determinado registro de um vetor de inteiro; cada registro contém um índice único que é utilizado para acessar o elemento do vetor. O problema: dada uma chave qualquer, localize o registro que contenha esta chave; O algoritmo de pesquisa mais simples é o que faz a pesquisa sequencial.

Seja f uma função de complexidade tal que f(n) é o número de registros consultados no arquivo, temos:

• Melhor caso: f(n) = 1 (registro procurado é o primeiro consultado);

• Pior caso: f(n) = n (registro procurado é o último consultado ou não está presente no arquivo);

• Caso médio: f(n) = (n+1)/2 (a média aritmética entre o melhor e o pior caso);

Além disso, a análise de algoritmos estuda certos paradigmas como divisão e conquista, programação dinâmica, gula, busca local, aproximação, entre outros que se mostraram úteis na criação de algoritmos para vários problemas computacionais.

Conclusão

Neste artigo, vimos uma breve introdução do que se trata a análise de algoritmos. Como ela é útil para definir o algoritmo mais eficiente em determinados problemas. Assim, o objetivo final não é apenas fazer códigos que funcionem, mas que sejam também eficientes.

“Um bom algoritmo, mesmo rodando em uma máquina lenta, sempre acaba derrotando (para instâncias grandes do problema) um algoritmo pior rodando em uma máquina rápida. Sempre.” - S. S. Skiena, The Algorithm Design Manual

Um abraço e até a próxima!

Curso Acessibilidade - Introdução

Conhecer o curso