Voltar aos artigos
A análise e o projeto de algoritmos são etapas fundamentais no desenvolvimento de soluções eficientes para problemas computacionais. Dois paradigmas clássicos se destacam nesse contexto: a programação dinâmica e os algoritmos gulosos.
Programação Dinâmica
Apesar do nome, programação dinâmica não está diretamente relacionada à programação de computadores, mas sim ao planejamento estratégico para resolução de problemas. Trata-se de um paradigma que consiste em decompor um problema em subproblemas menores, geralmente sobrepostos, e armazenar as soluções desses subproblemas em uma tabela para reutilização posterior.
Um princípio central da programação dinâmica é o princípio da otimalidade: em uma solução ótima para o problema original, as soluções dos subproblemas também devem ser ótimas. Essa abordagem evita o retrabalho, pois cada subproblema é resolvido apenas uma vez, e sua solução é reutilizada sempre que necessário.
Algoritmos Gulosos
Os algoritmos gulosos, por sua vez, seguem uma estratégia diferente: em cada etapa, escolhem a opção que parece ser a melhor naquele momento, na esperança de que essa escolha local leve a uma solução global ótima. Essa abordagem é bastante utilizada em problemas de otimização devido à sua simplicidade e baixa complexidade de implementação.
No entanto, é importante destacar que algoritmos gulosos nem sempre garantem a melhor solução global, pois as escolhas feitas não são reconsideradas posteriormente (não há rollback). Em geral, cada elemento do conjunto de possíveis escolhas é analisado apenas uma vez, e uma função de seleção determina qual elemento será incluído na solução naquele instante.
Análise de Algoritmos
Após projetar um algoritmo, é essencial testá-lo e analisá-lo para garantir sua corretude. Em seguida, realiza-se a análise de desempenho, especialmente em relação ao tempo de execução. Para isso, consideram-se diferentes cenários de entrada:
- Pior caso
- Caso médio
- Melhor caso
O objetivo é identificar a ordem de grandeza da função de tempo do algoritmo, conhecida como ordem de complexidade. Em outras palavras, o tempo de execução é uma medida da complexidade do algoritmo.
Notação Big-O
A notação Big-O é utilizada para expressar o limite assintótico superior do tempo de execução de um algoritmo. Diferentemente da notação Teta, que define limites superior e inferior, e da notação Ômega, que define apenas o limite inferior, a notação Big-O foca no comportamento da função para valores grandes de n.
Graficamente, temos:
A definição formal é:
Quando dizemos que f(n) é O(g(n)), estamos indicando que f(n) pertence ao conjunto O(g(n)).
Qualquer função linear an+b está em O(n²) e isso pode ser demonstrado escolhendo:
e:
25th abril 2019
