Análise Assintótica

A ordem de crescimento descrita neste artigo anterior 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:

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

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:

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:

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.

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:

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:

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²).