fbpx

Notação Big Ômega (análise de algoritmos)

Conheça todos os detalhes da notação Big Ômega: a segunda das 3 principais notações usadas em análise de algoritmos para representar desempenho.

compartilhe este artigo

Compartilhar no facebook
Compartilhar no twitter
Compartilhar no linkedin
Compartilhar no email

compartilhe este artigo

Compartilhar no facebook
Compartilhar no twitter
Compartilhar no linkedin
Compartilhar no whatsapp
Compartilhar no email

Introdução à notação Big Ômega

No último artigo conhecemos a primeira notação utilizada na ciência da computação para definir comportamento assintótico de algoritmos. A notação Big O. Neste artigo te ensinaremos a segunda notação computacional utilizada para a análise de algoritmos: a notação Big Ômega (ou apenas Ômega), representada pela letra grega Ω.

Se você ainda não leu o artigo sobre a notação Big O, clique neste link e acesse o artigo onde explicamos detalhadamente sobre o assunto. É altamente recomendado que você tenha algum conhecimento sobre a notação Big O antes de ler este artigo!

Da maneira mais objetiva possível, a notação Ω nos fornece uma simbologia simplificada para representar um limite inferior de desempenho para um algoritmo. Um limite mínimo de tempo que um algoritmo leva para ser executado. Ou seja, a notação Ω é o inverso da notação Big O.

Vamos a alguns exemplos práticos para você começar a compreender o significado e o uso da notação Ω.

Exemplo para função linear

Quando dizemos que a função 4n-3 é Ω(n) (lê-se “é ômega de n”), estamos afirmando que o comportamento assintótico de uma função linear é igual ou inferior ao dela. Significa dizer: a função 4n-3 nunca terá um comportamento de crescimento inferior ao de uma função com o comportamento linear. Desta forma, Ω(n) apresenta-se como um limite inferior, e sabemos que a função nunca apresentará um comportamento de crescimento que seja ultrapassado por esse limite inferior.

Exemplo: para a função 4n-3, existe uma outra função de comportamento linear que a limita inferiormente. Perceba no gráfico abaixo que, para valores de n≥1, a função 4n-3 supera a função n.

notação-big-ômega-01

Da mesma forma, também é correto afirmar que 4n-3 é Ω(1), pois a função 4n-3 nunca apresentará um comportamento de crescimento que seja ultrapassado por um comportamento constante. Desta forma, Ω(1) também se apresenta como um limite assintótico inferior:

notação-big-ômega-02

Agora, seria errado dizer que 4n-3 é Ω(n2), pois a função 4n-3 nunca crescerá a ponto de ultrapassar o comportamento quadrático. Desta forma, Ω(n2) não se apresenta como um limite assintótico inferior:

notação-big-ômega-03

Resumindo:

4n-3 não é Ω(n2), pois não pode superar (limitar inferiormente) uma função quadrática.

4n-3 é Ω(n), pois pode superar (limitar inferiormente) uma função linear.

4n-3 é Ω(1), pois pode superar (limitar inferiormente) uma função constante.

Exemplo para função quadrática

Quando dizemos que a função 5n2-n-3 é Ω(n2), estamos afirmando que o comportamento assintótico de uma função quadrático é igual ou inferior ao dela. Significa dizer: a função 5n2-n-3 nunca terá um comportamento de crescimento inferior ao de uma função com o comportamento quadrático. Desta forma, Ω(n2) apresenta-se como um limite inferior, e sabemos que a função nunca apresentará um comportamento de crescimento que seja ultrapassado por esse limite inferior.

Exemplo: para a função 5n2-n-3, existe uma outra função de comportamento quadrático que a limita inferiormente. Perceba no gráfico abaixo que, para valores de n≥1, a função 5n2-n-3 supera a função n2.

notação-big-ômega-04

Da mesma forma, também é correto afirmar que 5n2-n-3 é Ω(n), pois a função 5n2-n-3 nunca apresentará um comportamento de crescimento que seja ultrapassado por um comportamento linear. Desta forma, Ω(n) também se apresenta como um limite assintótico inferior:

notação-big-ômega-05

Agora, seria errado dizer que 5n2-n-3 é Ω(n3), pois a função 5n2-n-3 nunca crescerá a ponto de ultrapassar o comportamento cúbico. Desta forma, Ω(n3) não se apresenta como um limite assintótico inferior:

notação-big-ômega-06

Resumindo:

5n2-n-3 não é Ω(n3), pois não pode superar (limitar inferiormente) uma função cúbica.

5n2-n-3 é Ω(n2), pois pode superar (limitar inferiormente) uma função quadrática.

5n2-n-3 é Ω(n), pois pode superar (limitar inferiormente) uma função linear.

Definição matemática formal da notação Big Ômega

Dada duas funções de complexidade de tempo de algoritmos: f(n) e g(n). A definição matemática formal estabelece que:

  • f(n) = Ω(g(n)) (lê-se “f de n é Ômega de g de n”) se existirem constantes positivas c e n0, tais que f(n) ≥ c.g(n) para todos os n ≥ n0.

Essa definição parece um pouco complicada de se compreender à primeira vista, mas vamos demonstrar com alguns exemplos práticos.

Primeiro exemplo do uso matemático da notação Big Ômega

Vamos tentar demonstrar pela definição que 4n+1 = Ω(n) (lê-se “é Ômega de n”).

Pela definição, tudo o que precisamos fazer é demonstrar que existe uma constante positiva c e um valor positivo n0 inicial de forma que, para todos os valores de n maiores ou igual a n04n+1 sempre seja maior ou igual a c multiplicado por n.

Em resumo: precisamos provar que 4n+1 ≥ c.n, para uma constante c positiva e um valor n0 inicial positivo.

Para tanto, a primeira decisão que precisamos tomar é escolher um valor para a constante c. Neste caso, vamos considerar c igual ao valor 4. Observe abaixo uma tabela que mostra os resultados da desigualdade para c=4 e para alguns valores de n:

análise-de-algoritmos-algorithm analysis-05

Observe que, para todos os valores de n expressos na tabela, a função do algoritmo 4n+1 é sempre uma unidade maior que c.n. Quando plotamos um gráfico para ambas as funções, visualizamos com maior clareza como a função 4n+1 cresce mais que a função c.n:

notação-big-ômega-07

Isso significa que Ω(n) representa um limite assintótico inferior para a função 4n+1, ou seja, existe uma constante c=4 e um n0=1, tal que 4n+1 ≥ c.n para todos os valores de n maiores ou igual a n0. Desta forma, está provado que, de fato, 4n+1 = Ω(n).

Segundo exemplo do uso matemático da notação Big Ômega

Vamos tentar demonstrar pela definição que 5n2-n-3 = Ω(n2) (lê-se “é Ômega de n ao quadrado”).

Pela definição, tudo o que precisamos fazer é demonstrar que existe uma constante positiva c e um valor positivo n0 inicial de forma que, para todos os valores de n maiores ou igual a n05n2-n-3 sempre seja maior ou igualc multiplicado por n2.

Em resumo, precisamos provar que 5n2-n-3 ≥ c.n2, para uma constante c e um valor n0 inicial.

Novamente, precisamos escolher um valor para a constante c. Neste caso, também vamos considerar c igual ao valor 4. Observe abaixo uma tabela que mostra os resultados da desigualdade para c=4 e para alguns valores de n:

análise-de-algoritmos-algorithm analysis-04

Observe que, para todos os valores de n>2 expressos na tabela, a função do algoritmo 5n2-n-3 é cada vez maior que c.n2. Quando plotamos um gráfico para ambas as funções, visualizamos com maior clareza como a função 5n2-n-3 cresce mais que a função c.n2.

notação-big-ômega-08

Isso significa que Ω(n2) representa um limite assintótico inferior para a função 5n2-n-3. ou seja, existe uma constante c=4 e um n0=1, tal que 5n2-n-3 ≥ c.n2 para todos os valores de n maiores ou igual a n0. Desta forma, está provado que, de fato, 5n2-n-3 = Ω(n2).

Terceiro exemplo: uma tentativa frustrada

Vamos tentar demonstrar pela definição que 2n+1 = Ω(n2).

Pela definição, tudo o que precisamos fazer é demonstrar que existe uma constante positiva c e um valor n0 inicial de forma que, para todos os valores de n maiores que n02n+1 sempre seja maior ou igual a c multiplicado por n2.

Em resumo, precisamos provar que 2n+1 ≥ c.n2, para uma constante c e um valor n0 inicial.

À primeira vista, percebe-se que 2n+1 possui comportamento linear e c.n2 possui comportamento quadrático. Por isso somos tentados a afirmar que essa demonstração é falsa, pois uma função quadrática (c.n2) não pode representar um limite assintótico inferior para uma função linear (2n+1). Mas vamos realizar uma análise mais aprofundada para perceber o motivo dessa impossibilidade.

Vamos realizar algumas transformações algébricas no âmbito de isolar a constante c na inequação e perceber os seus possíveis valores:

análise-de-algoritmos-algorithm analysis-03

A inequação resultante já nos mostra a impossibilidade de existir alguma constante c que torne a expressão válida para grandes valores de n (n→∞), pois, independentemente do quão grande for o valor de c, o denominador n2 sempre irá tornar o resultado da função cada vez menor.

Observe na tabela abaixo como o valor da função fica cada vez menor quando comparado com o valor de c (considerando c=1, que é o seu valor mínimo). Pode-se perceber que os valores da função se aproximam de zero ao passo que o valor de n cresce.

análise-de-algoritmos-algorithm analysis-01

Ou seja, mesmo com o menor valor possível para a constante c, a função sempre irá diminuir a ponto de se tornar menor que a constante.

Portanto, não conseguimos demonstrar o nosso objetivo. Não existe uma constante c e um n0, tal que 2n+1 ≥ c.n2 para todos os valores de n maiores ou igual a n0. Desta forma, está provado que, de fato, 2n+1 ≠ Ω(n2) (lê-se “não é Ômega de n ao quadrado”).

Exercícios

Tente demonstrar matematicamente que n2+800 = Ω(n).

Tente demonstrar matematicamente que 2n+10 = Ω(n).

Tente demonstrar matematicamente que n+10 = Ω(n2).

Tente demonstrar matematicamente que 7n-2 = Ω(1).

Tente demonstrar matematicamente que n2+20n+5 = Ω(n3).

compartilhe este artigo

Compartilhar no facebook
Compartilhar no twitter
Compartilhar no linkedin
Compartilhar no email
Compartilhar no facebook
Compartilhar no twitter
Compartilhar no linkedin
Compartilhar no whatsapp
Compartilhar no email

Sobre o autor

Almir Santiago

Almir Santiago

MSc in Systems and Computing, Professor of Computer Programming, Algorithms and Data Structures.

Deixe um comentário