Análise de algoritmos

Complexidade de algoritmo se tem dois tipos de algoritmos: Espacial e Temporal.

A espacial analisa os recursos para resolver problemas.

A temporal analisa o tempo utilizado pelo algoritmo.

Com a analise da complexidade de algoritmos é possivel verificar a sua eficiência.

Um algoritmo é considerado eficiênte quando completa uma tarefa com o menor tempo e utiliza menos recursos possiveis.

A analise de algortimos é classificada em:

Ômega(Ω):

Define-se como o melhor caso:

É o menor tempo de execução em uma entrada de tamanho N.

Theta Θ :

Define-se como caso médio:

Obtém a média do tempo de execução de todas as entradas de tamanho N.

Ômicron (O):

Define-se como o pior caso.

Baseia-se no maior tempo de execução das entradas N(mais utilizado).

Se divide em classes:

Constante O(1):

Constantes algoritmos de complexidade O (1), independente das entradas N.

É o único que as instruções dos algoritmos são executadas em um tamanho fixo de vezes.

Logaritma O(log n):

Usa quando se resolve problemas grandes transformando-os em pequenos.O tempo de execução é menor do que uma constante grande.

Linear O(n):

São algoritmos de complexidade.

Uma operação é realizada em cada elemento de entrada.

NLogN O(n log n):

Como o próprio nome diz, são algoritmos que têm complexidade O (NLogn)

Ocorre tipicamente em algoritmos que dividem o problema em problemas menores, porem juntando posteriormente a solução dos problemas menores.

Complexidade Quadrática O(n2) :

Algoritmos com essa complexidade ocorre quando os itens são processados em pares, como uma laço dentro do outro.

Complexidade Cubica O(n3):

Serve apenas para resolver problemas pequenos.

Complexidade Exponencial O(2n):

São problemas com solução que se usa força bruta para resolvê-los, não são úteis ao ponto de vista prático.

Passo 3:

Comparar uma função linear f(n) com uma função quadrática g(n) e mostre que f(n) é Ômicron (g(n)), determine constantes n0 natural e c real positivo.

f(n)= O(g(n)) = c =