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: f₁ (n) = 2n² + 5n operações

Algoritmo 2: f₂ (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 f₁ (n) cresce com n 2 ao passo que f₂ (n) cresce com n. Um crescimento quadrático é considerado pior que um crescimento linear. Assim, vamos preferir o Algoritmo 2 ao Algoritmo 1.