Complexidade de Algoritmos
Links relacionados: Linguagens de Programação
Introdução
Por meio da complexidade dos algoritmos é possível:
- projetar algoritmos eficientes;
- analisar a complexidade de um algoritmo existente para verificar sua eficiência;
- projetar algoritmos eficientes desde sua concepção.
Por exemplo, imagine que n um parâmetro de entrada de um algoritmo que define a quantidade de números a ordenar. Como comparar dois algoritmos para poder decidir qual desses é melhor?
Para tal, é importante que haja alguma forma mensurável de expressar eficiência de um algoritmo. Uma forma de se medir a eficiência é em relação ao tempo de execução ou o espaço (memória) utilizado.
Na análise de algoritmos, conta-se o número de operações realizadas pelo algoritmo que são consideradas relevantes. Esse número de operações são expressos por uma função de n, podendo ser comparações, operações aritméticas, movimentos de dados, etc.
O número de operações realizadas por um determinado algoritmo pode depender da particular instância da entrada. Em geral interessa-nos o pior caso, isto é, o maior número de operações usadas para qualquer entrada de tamanho n.
Análises também podem ser feitas para o melhor caso e o caso médio. Neste último, supõe-se conhecida uma certa distribuição da entrada.
Exemplo
Busca sequencial de um dado elemento em um vetor armazenando n elementos de forma aleatória. Discuta o pior caso, melhor caso e o caso médio. No caso médio suponha a distribuição uniforme e que o dado buscado está dentro do vetor. Como muda o caso médio se o dado em geral não está presente?
Exemplo
Considere o número de operações de cada um dos dois algoritmos que resolvem o mesmo problema, como função de n.
Algoritmo 1: f1 (n) = 2n2 + 5n operações
Algoritmo 2: f2 (n) = 500n + 4000 operações
Dependendo do valor de n, o Algoritmo 1 pode requerer mais ou menos operações que o Algoritmo 2.
(Compare as duas funções para n = 10 e n = 100.)
Um caso de particular interesse é quando n tem valor muito grande (n → ∞), denominado comportamento assintótico.
Os termos inferiores e as constantes multiplicativas contribuem pouco na comparação e podem ser descartados.
O importante é observar que f1 (n) cresce com n 2 ao passo que f2 (n) cresce com n. Um crescimento quadrático é considerado pior que um crescimento linear. Assim, vamos preferir o Algoritmo 2 ao Algoritmo 1.