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.

Nos siga em nossas redes sociais.

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.

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:

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:

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ática é 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.

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:

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:

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:

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:

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:

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.

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:

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.

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

Nos siga
em nossas redes sociais.

Nos siga em nossas redes sociais.

Deixe um comentário