Análise Assintótica

Análise Assintótica

Se baseia na definição de três pontos relevantes entre todas as possibilidades de uso de um algoritmo: o pior caso possível, o melhor caso possível e o caso médio.

A análise assintótica de um algoritmo representado por uma função $f(n)$ refere-se a taxa de crescimento de $f(n)$ à medida que $n$ cresce.

Análise Assintótica

Imagine, que temos dois algoritmos, um que pode ser representado por uma função linear, $f_1 (n)=d×n+k$, ou seja, para cada $n$, o tempo necessário para seu processamento será dado pela cardinalidade do conjunto multiplicada por uma constante $d$ qualquer e este resultado somado a outra constante $k$, usando as mesmas constantes poderíamos ter um algoritmo dado pela função exponencial $f_1 (n)=d×n^2+k$.

Análise Assintótica

Análise Assintótica

Análise Assintótica

Quanto custa um automóvel mais um skate?

Análise Assintótica

A principal vantagem da notação Big-O é que podemos desconsiderar todos os termos da equação polinomial que represente o algoritmo, por exemplo nas funções $f_1 (n)=d×n+k$, e $f_1 (n)=d×n^2+k$, podemos desprezar o $k$ antes mesmo de começar.

Análise Assintótica

Análise Assintótica

Análise Assintótica

$$(n − 1) + (n − 2) + (n − 3) … + 3 + 2 + 1$$

$$\frac{n(n-1)}{2} ∴ \frac{n^2}{2}-\frac{n}{2}$$

$$𝑂(n^2)$$