Estruturas de dados - análise assintótica

A análise assintótica de um algoritmo refere-se à definição do limite / enquadramento matemático de seu desempenho em tempo de execução. Usando a análise assintótica, podemos muito bem concluir o melhor caso, o caso médio e o pior caso de um algoritmo.

A análise assintótica é limitada pela entrada, ou seja, se não houver entrada para o algoritmo, conclui-se que ele funciona em um tempo constante. Além da "entrada", todos os outros fatores são considerados constantes.

A 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 (n ² ). Isso significa que o tempo de execução da primeira operação aumentará linearmente com o aumento den e o tempo de execução da segunda operação aumentará exponencialmente quando naumenta. Da mesma forma, o tempo de execução de ambas as operações será quase o mesmo sen é significativamente pequeno.

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

Best Case - Tempo mínimo necessário para a execução do programa.
Average Case - Tempo médio necessário para a execução do programa.
Worst Case - 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 n₀ such that f(n) ≤ c.g(n) for all n > n₀. }

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 n₀ such that g(n) ≤ c.f(n) for all n > n₀. }

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 > n₀. }

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 ² )
cúbico	-	Ο (n ³ )
polinomial	-	n ^{Ο (1)}
exponencial	-	2 ^{Ο (n)}