Complexibilidade de Algoritmos

Complexibilidade de Algoritmos

1. Constante

   • O uso do algoritmo independe do tamanho da entrada, ou seja, todas as instruções são executadas um número fixo de vezes, independente do tamanho da entrada.

2. Logarítmica

   • Tipicamente para algoritmos que resolvem um problema transformando-o em problemas menores. Se a entrada dobrar de tamanho, o tempo de execução aumenta de uma unidade, ou seja, para o tempo de execução dobrar, a entrada deve ser n2.

3. Linear

   • Em geral um pequeno trabalho é realizado sobre cada elemento de entrada. Esta é a melhor situação possível para algoritmos que têm que processar os n elementos da entrada ou produzir n elementos de saída. Cada vez que n dobrar de tamanho, o tempo de execução dobra.

4. n log n,

   • Ocorre para algoritmos que resolvem o problema quebrando-o em problemas menores, resolvendo cada um deles independente e depois juntando as soluções. Cada vez que n dobrar de tamanho, o tempo de execução será maior que o dobro.

5. Quadrática

   • Ocorre quando os itens são processados aos pares, muitas vezes com um laço dentre de outro. São muito úteis para resolver problemas relativamente pequenos. Cada vez que n dobrar de tamanho, o tempo de execução será multiplicado por 4.

6. Cúbica

   • São úteis apenas para problemas pequenos. Cada vez que n dobrar de tamanho, o tempo de execução será multiplicado por 8.

7. Exponencial

   • Geralmente não são úteis, pois ocorrem na solução de problemas quando se usa a força bruta. Cada vez que n dobrar de tamanho, o tempo de execução será elevado ao quadrado.