Neste tutorial, você aprenderá o que são notações assintóticas. Além disso, você aprenderá sobre a notação Big-O, notação Theta e notação Omega.
A eficiência de um algoritmo depende da quantidade de tempo, armazenamento e outros recursos necessários para executar o algoritmo. A eficiência é medida com a ajuda de notações assintóticas.
Um algoritmo pode não ter o mesmo desempenho para diferentes tipos de entradas. Com o aumento do tamanho da entrada, o desempenho mudará.
O estudo da mudança no desempenho do algoritmo com a mudança na ordem do tamanho da entrada é definido como análise assintótica.
Notações assintóticas
As notações assintóticas são as notações matemáticas usadas para descrever o tempo de execução de um algoritmo quando a entrada tende para um determinado valor ou valor limite.
Por exemplo: Na classificação por bolha, quando a matriz de entrada já está classificada, o tempo gasto pelo algoritmo é linear, ou seja, o melhor caso.
Mas, quando a matriz de entrada está na condição reversa, o algoritmo leva o tempo máximo (quadrático) para classificar os elementos, ou seja, o pior caso.
Quando a matriz de entrada não está classificada nem na ordem inversa, leva um tempo médio. Essas durações são indicadas por notações assintóticas.
Existem principalmente três notações assintóticas:
- Notação Big-O
- Notação Omega
- Notação teta
Notação Big-O (notação O)
A notação Big-O representa o limite superior do tempo de execução de um algoritmo. Portanto, ele fornece a complexidade do pior caso de um algoritmo.
Big-O fornece o limite superior de uma função
O (g (n)) = (f (n): existem constantes positivas c e n 0 tais que 0 ≦ f (n) ≦ cg (n) para todo n ≧ n 0 )
A expressão acima pode ser descrita como uma função f(n)pertencente ao conjunto O(g(n))se existir uma constante positiva ctal que esteja entre 0e cg(n), para suficientemente grande n.
Para qualquer valor de n, o tempo de execução de um algoritmo não ultrapassa o tempo fornecido por O(g(n)).
Uma vez que fornece o pior caso de tempo de execução de um algoritmo, é amplamente usado para analisar um algoritmo, pois estamos sempre interessados no pior cenário.
Notação Omega (notação Ω)
A notação Omega representa o limite inferior do tempo de execução de um algoritmo. Assim, ele fornece o melhor caso de complexidade de um algoritmo.
Omega fornece o limite inferior de uma função
Ω (g (n)) = (f (n): existem constantes positivas c e n 0 tais que 0 ≦ cg (n) ≦ f (n) para todo n ≧ n 0 )
A expressão acima pode ser descrita como uma função f(n)pertencente ao conjunto Ω(g(n))se existir uma constante positiva ctal que esteja acima cg(n), para suficientemente grande n.
Para qualquer valor de n, o tempo mínimo exigido pelo algoritmo é fornecido pelo Omega Ω(g(n)).
Notação Theta (notação Θ)
A notação Theta inclui a função de cima e de baixo. Uma vez que representa o limite superior e inferior do tempo de execução de um algoritmo, é usado para analisar a complexidade de caso médio de um algoritmo.
Theta limita a função dentro de fatores constantes
Para uma função g(n), Θ(g(n))é dado pela relação:
Θ (g (n)) = (f (n): existem constantes positivas c 1 , c 2 e n 0 tais que 0 ≦ c 1 g (n) ≦ f (n) ≦ c 2 g (n) para todos n ≧ n 0 )
A expressão acima pode ser descrita como uma função f(n)pertencente ao conjunto Θ(g(n))se existirem constantes positivas e de tal forma que ela possa ser imprensada entre e , para n suficientemente grande.c1c2c1g(n)c2g(n)
Se uma função f(n)está em qualquer lugar entre e para todos , então é dito que é um limite assintoticamente rígido.c1g(n)c2g(n)n ≧ n0f(n)
