Noções de Complexidade de Algoritmos

A avaliação de desempenho de um algoritmo quanto executado por um computador pode ser feita a posteriori ou a priori.

Uma avaliação a posteriori envolve a execução propriamente dita do algoritmo, medindo-se o tempo de execução. Só pode ser exata se se conhecer detalhes da arquitetura da máquina, da linguagem de programação usada, do código gerado pelo compilador, etc. De fato, o tempo deve ser medido fisicamente para um certo algoritmo, compilador e computador.

Já uma avaliação a priori de um algoritmo, feita sem sua execução, de forma analítica, é possível se considerarmos dois itens: a entrada (os dados fornecidos) e o número de instruções executadas pelo algoritmo.

Tempo de execução

O tempo de execução de um algoritmo pode ser dado como uma função T(n) do tamanho n da sua entrada.

Um programa pode ter tempo de execução T(n) = n*n + n + 1.

A unidade de T(n) é em principio instrução executada. Uma instrução neste contexto é uma seqüência de operações cujo tempo de execução pode ser considerado constante (de certa forma, cada “passo” do algoritmo).

Consideremos o algoritmo abaixo:

void somavet (int v[n], int *k) {

int i;

*k=0;

for (i=0; i<n; i++)

*k = (*k) + v[i];

}

Sendo v a entrada, de tamanho n, pode-se ver facilmente que a soma k+v[i] será efetuada n vezes.

Conseqüentemente, T(n) = n+1, incluindo o passo de inicialização. O tempo de execução (em instruções) variará conforme variar n, numa proporção linear.

No entanto, o tempo de execução vai depender de outros fatores, ligados à máquina, linguagens usadas, etc., e mesmo, por vezes, é função de aspectos adicionais de uma particular entrada e não apenas do seu tamanho, como no exemplo a seguir:

int localiza (int v[n], int x) {

int i;

for (i=0; i<n; i++)

if (x==v[i])

return i;

return -1;

}

O teste pode ser executado apenas uma vez, se o valor procurado estiver no primeiro elemento do vetor. E é executado no máximo n vezes. Pode-se cogitar, então, de tempos mínimos, médios e máximos.

Em geral, tempos mínimos são de pouca utilidade e tempos médios são difíceis de calcular.

Considera-se assim T(n) como uma medida assintótica máxima, ou seja, uma medida do pior caso de desempenho, que ocorre com a entrada mais desfavorável possível. No caso anterior, T(n) = n + 1, incluindo o passo de retorno, que sempre acontece uma vez.

Complexidade de Algoritmo

A avaliação analítica de uma algoritmo pode ser feita com vistas a se obter uma estimativa do esforço de computação, não em termos de unidade de tempo propriamente, mais em termos de uma taxa de crescimento do tempo de execução em função do “tamanho do problema”, i.e., do tamanho da entrada.

Um exemplo típico desse relacionamento entre tamanho da entrada e tempo de processamento é o caso dos algoritmos de ordenação: nestes, os dados são vistos sempre como sequências de valores com um certo comprimento, e é natural concluir que quanto maior esse seqüência, mais tempo consumirá a ordenação.

Como já se discutiu para o tempo de execução, pode-se ter complexidade de melhor, médio e pior caso.

A expressão da complexidade de um algoritmo busca refletir suas condições intrínsecas, abstraindo aspectos ligados aos ambientes específicos de execução. Assim, não são consideradas constantes de soma ou multiplicação. Uma expressão como kn + c deve ser simplificada para n.

A Notação O

No trabalho com estruturas de dados são as seguintes as complexidades costumeiras (em ordem crescente):

• • O(1) ou constante;

  • O(log n) ou logaritímica;

  • O(n) ou linear;

  • O(n log n) ou n log de n;

  • O(n²) ou quadrática;

  • O(n³) ou cúbica.

Fonte: http://www.univasf.edu.br/~marcelo.linder/arquivos_ed1/aulas/aula21.pdf