Python - Tipos de Algoritmo

A eficiência e a precisão dos algoritmos devem ser analisadas para compará-los e escolher um algoritmo específico para determinados cenários. O processo de fazer essa análise é chamado de análise assintótica. Refere-se ao cálculo do tempo de execução de qualquer operação em unidades matemáticas de computação. Por exemplo, o tempo de execução de uma operação é calculado como f (n) e pode ser para outra operação é calculado como g (n2). Isso significa que o tempo de execução da primeira operação aumentará linearmente com o aumento em n e o tempo de execução da segunda operação aumentará exponencialmente quando n aumentar. Da mesma forma, o tempo de execução de ambas as operações será quase o mesmo se n for significativamente pequeno.

Normalmente, o tempo exigido por um algoritmo cai em três tipos -

• Melhor caso - tempo mínimo necessário para a execução do programa.
• Caso Médio - Tempo médio necessário para a execução do programa.
• Pior caso - tempo máximo necessário para a execução do programa.

Notações assintóticas

A seguir estão as notações assintóticas comumente usadas para calcular a complexidade do tempo de execução de um algoritmo.

• Ο Notação
• Ω Notação
• Notação θ

Big Oh Notation, Ο

A notação Ο (n) é a maneira formal de expressar o limite superior do tempo de execução de um algoritmo. Ele mede o pior caso de complexidade de tempo ou a maior quantidade de tempo que um algoritmo pode levar para ser concluído.

Por exemplo, para uma função f(n)

Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c.g(n) for all n > n0. }

Notação Omega, Ω

A notação Ω (n) é a maneira formal de expressar o limite inferior do tempo de execução de um algoritmo. Ele mede o melhor caso de complexidade de tempo ou a melhor quantidade de tempo que um algoritmo pode levar para ser concluído.

Por exemplo, para uma função f(n)

Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. }

Notação Theta, θ

A notação θ (n) é a maneira formal de expressar o limite inferior e o limite superior do tempo de execução de um algoritmo. É representado da seguinte forma -

θ(f(n)) = { g(n) if and only if g(n) =  Ο(f(n)) and g(n) = Ω(f(n)) for all n > n0. }

Notações assintóticas comuns

A seguir está uma lista de algumas notações assintóticas comuns -

constante	-	Ο (1)
logarítmico	-	Ο (log n)
linear	-	Ο (n)
n log n	-	Ο (n log n)
quadrático	-	Ο (n 2 )
cúbico	-	Ο (n 3 )
polinomial	-	n Ο (1)
exponencial	-	2 Ο (n)