Análise Assintótica
Tags: algorithms, programming, braziliandevs, beginners
Published: 2023-01-02 18:28:39

A ordem de crescimento descrita neste [artigo anterior](https://dev.to/feministech/analise-de-algoritmos-para-iniciantes-pp3) descreve apenas a eficiencia da performance de algoritmos alternativos. O objetivo da análise de algoritmos é conseguir uma medida que não seja tão precisa, para calcular o tempo computacional de um algoritmo.

Isso não é uma tarefa fácil como vimos. A notação assintótica na complexidade de algoritmos é identificar classes de algoritmos que possuem comportamento similar.

**O que é Notação Assintótica?**

Para entender melhor as palavras eu venho buscando a etimologia, a origem e os significados das palavras. 

**Notação** é o nome que se dá ao método de representar mensagens por meio de símbolos.
**Assíntótica**, próprio de assíntota, da linha que, numa curva plana, expressa uma distância infinita em relação ao ponto P.

As notações que usamos para descrever o tempo de execução assintótica de um algoritmo são definidas em termos de **funções** cujos domínios são o conjunto dos números naturais N = {O,1,2, ...). Tais notações são convenientes para descrever a função do tempo de execução do pior caso T(n), que em geral é definida sobre o tamanhos da entrada.

**Em outras palavras, notação assintótica é uma representação simbólica por meio de funções do tempo de execução de um algoritmo.**

Contudo, as vezes é conveniente abusar da notação assintótica de várias maneiras. Por exemplo, a notação é estendida com facilidade ao domínio dos números reais ou, de modo alternativo, limitado a um subconjunto dos números naturais. Porém, é importante entender o significado preciso da notação para que, quando houver um abuso em seu uso, ela não seja mal utilizada.

Toda vez que falarmos função neste artigo, estaremos nos referindo a uma função de equação matemática.

**Notação Θ ou Notação Tetha**

Digamos que se uma função f(n) está entre os valores c2 * g(n) e c1 * g(n) para duas constantes c1 e c2. Traduzindo, uma função qualquer está entre duas funções iguais multiplicadas por constantes diferentes. Essa função f(n) pertence ao grupo (g(n)).

Então diz-se que a função g(n) é um limite assintóticamente restrito para f(n). Formalmente falando em uma descrição matemática:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qc729ldqze3hd2q64d37.png)

Ao representar esta equação em um gráfico matemático:

![Exemplo da aplicação da notação assintótica Θ.](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8dg9ep97plysp1z73vr8.png)

Figura 2 – Exemplo da aplicação da notação assintótica Θ.

Por força de representação, é comum considerar que f(n) = (g(n)) (lê-se “f de n é téta de g de n”) , que traduzindo, a função F de n é igual ao Tetha da função G de n.

Embora o correto seja f(n)  (g(n)) que a função F pertence ao limite assintótico do Tetha da função G. 

Exemplos de duas funções que se encaixam na condição f(n)  (g(n)):

f(n) = 12n²-3n 
g(n) = n² 

Lembra como simplificamos a equação no artigo anterior apenas para o termo principal da fórmula? Aqui têm outro exemplo.

f(n) = 100n³-n² +3.5n - 17 
g(n) = n³ 

**Notação O ou Notação Big O**

Se uma função f(n) possui como limite assintótico superior o valor g(n), então diz-se que f(n) pertence ao grupo O(g(n)). Também pode se dizer que g(n) é o limite assintótico superior para f(n). Formalmente falando em uma descrição matemática:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1anc1ls8tuad53cm85ni.png)


![Exemplo da aplicação da notação assintótica O.](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ifaw3h8nms0fp5fet1cj.png)

Exemplo da aplicação da notação assintótica O.

Também é preciso ter em mente que se f(n)  (g(n)) , então a mesma função também pertence a (g(n)), ou seja f(n)  O(g(n)) .

A notação O é usada sempre para informar qual é o pior caso da complexidade de um algoritmo.

Desse modo, quando se diz que “a complexidade de um algoritmo é O(n²) (lê se Big O de Ene ao Quadrado)” que o algoritmo demandará tempo de pior caso c*n² para uma entrada de tamanho n.

Exemplos de duas funções que se encaixam na condição f(n)  O(g(n)):

f(n) = 14n²-n 
g(n) = n² - 6n 

Lembra como simplificamos a equação no artigo anterior apenas para o termo principal da fórmula? Aqui têm outro exemplo.

f(n) = 100n³-n² +3.5n - 17 
g(n) = 2n+3n² 

**Notação Ω ou Notação Ômega**

Se uma função f(n) possui como limite assintótico inferior o valor g(n), então diz-se que f(n) pertence ao grupo (g(n)). Também pode se dizer que g(n) é o limite assintótico inferior para f(n). Formalmente falando em uma descrição matemática:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5eg75mnoiy67jewcigzk.png)


![Exemplo da aplicação da notação assintótica ­Ω.](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/tfvbccltkykx5rlmvucv.png)

Exemplo da aplicação da notação assintótica ­Ω.

Teorema é uma proposição a ser provada, ou que pode ser demonstrada por meio de um processo lógico. É importante para quem está cursando a matéria de algoritmos conheça esses teoremas, que podem ser usados para provar outros teoremas.

Para quaisquer funções f(n) e g(n), f(n)  (g(n)) se f(n)  O(g(n)) e f(n)  (g(n))  

Repare que essa é uma preposição lógica.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1hs4dfyl7xzql6se7qne.png)

**Notação o**

Se uma função f(n) possui como limite assintótico não é justo a g(n), então diz-se que f(n) pertence ao grupo o(g(n)). Também pode se dizer que g(n) é o limite assintótico inferior para f(n). Formalmente falando em uma descrição matemática:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jwucqbmjsftsxfaunr3b.png)

**Notação ω**

Se uma função f(n) possui como limite assintótico não é justo a g(n), então diz-se que f(n) pertence ao grupo o(g(n)). Também pode se dizer que g(n) é o limite assintótico inferior para f(n). Formalmente falando em uma descrição matemática:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/agq48w72b8cn071f5c0w.png)

**Propriedades das Notações**

É necessário possuir algum conhecimento lógico e de equações matemáticas para entender as propriedades abaixo.

**Transitividade**

f(n) ∈ Θ(g(n)) e g(n) ∈ Θ(h(n)) implicam que f(n) ∈ Θ(h(n));

f(n) ∈ O(g(n)) e g(n) ∈ O(h(n)) implicam que f(n) ∈ O(h(n));

f(n) ∈ Ω(g(n)) e g(n) ∈ Ω(h(n)) implicam que f(n) ∈ Ω(h(n));

f(n) ∈ o(g(n)) e g(n) ∈ o(h(n)) implicam que f(n) ∈ o(h(n))

**Reflexividade**

f(n) ∈ Θ(f(n));

f(n) ∈ O(f(n));

f(n) ∈ Ω(f(n));

**Simetria**

f(n) ∈ Θ(g(n)) se e somente se g(n) ∈ Θ(f(n)).

**Simetria de Transposição**

f(n) ∈ O(g(n)) se e somente se se g(n) ∈ Ω(f(n));

f(n) ∈ o(g(n)) se e somente se se g(n) ∈ ω(f(n)).

**Existe uma analogia dessa relação entre funções com as comparações entre os números reais a e b que te facilita a entender o limite das funções**

f(n) ∈ O(g(n)) é como a ≤ b;

f(n) ∈ Ω(g(n)) é como a ≥ b;

f(n) ∈ Θ(g(n)) é como a=b;

f(n) ∈ o(g(n)) é como a<b;

f(n) ∈ ω(g(n)) é como a>b.

**Na multiplicação por uma constante funciona-se a seguinte regra. Ignora-se o valor da constante.**

Θ(c f(n)) = Θ(f(n));

99n² ∈ Θ(n²).

**O maior grau de um polinômio é o que é utilizado para representar a notação assintótica**

3n³ −5n² +100 ∈ Θ(n³);

6n^4 −20n² +100 ∈ Θ(n4);

0,8n +224 ∈ Θ(n).

**Na ordem do termo dominante**

2n +6n³ ∈ Θ(2n);

n! - 3n² ∈ Θ(n!);

n log n +3n² ∈ Θ(n²).