Notação Theta (análise de algoritmos)

Conheça todos os detalhes da notação Theta: a última das 3 principais notações usadas em análise de algoritmos para representar desempenho.

Nos siga em nossas redes sociais.

Introdução à notação Theta

No último artigo conhecemos a segunda notação computacional utilizada em análise de algoritmos para definir o comportamento assintótico dos algoritmos: a notação Ω (Ômega). Neste artigo te ensinaremos a terceira notação computacional utilizada para definir matematicamente o comportamento assintótico de algoritmos: a notação Theta, representada pela letra grega Θ.

Se você ainda não leu o artigo sobre a notação Ω (Ômega), 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 e Ω (Ômega) antes de ler este artigo!

Da maneira mais objetiva possível, a notação Θ nos fornece uma simbologia simplificada para representar um limite justo de desempenho para um algoritmo. Um limite exato de tempo que um algoritmo leva para ser executado. Ou seja, a notação Θ representa o ponto de encontro entre as notações Ω (limite inferior) e Big O (limite superior).

Definição matemática formal da notação Theta

Diferentemente do que fizemos para os artigos sobre as notações Ω e Big O, vamos abordar a definição matemática da notação Θ antes de partirmos para os exemplos.

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 é téta de g de n”) se existirem duas constantes positivas c1 e c2 e um valor n0, tais que c1.g(n) ≤ f(n) ≤ c2.g(n) para todos os n ≥ n0.

Ou seja, se ele for limitado superiormente e inferiormente pela mesma função g(n). Vamos demonstrar com alguns exemplos ilustrados.

Primeiro exemplo do uso matemático da notação Theta

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

Pela definição, tudo o que precisamos fazer é demonstrar que existem duas constantes positivas c1 e c2 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 igualc1 multiplicado por n e menor ou igualc2 multiplicado por n (ao mesmo tempo).

Em resumo: precisamos provar que c1.n ≤ 4n+1 ≤ c2.n, para constantes c1 e c2 positivas e um valor n0 inicial positivo.

Para tanto, a primeira decisão que precisamos tomar é escolher valores para as constantes c1 e c2. Neste caso, vamos considerar c1 sendo igual ao valor 4c2 sendo igual ao valor 5. Observe abaixo uma tabela que mostra os resultados da desigualdade para alguns valores de n:

Observe que, para todos os valores de n ≥ 1 expressos na tabela, a função do algoritmo 4n+1 é sempre maior que 4n e menor ou igual a 5n. Quando plotamos um gráfico para ambas as funções, visualizamos com maior clareza como a função 4n+1 é limitada superiormente pela função 5n e inferiormente pela função 4n:

Isso significa que a função 4n+1 nunca terá um comportamento de crescimento inferior a 4n e nem crescerá mais que 5n. Por este motivo dizemos que Θ(n) representa um limite assintótico justo para a função 4n+1, porque ela é limitada superiormente e inferiormente por duas outras funções de uma mesma classe assintótica, a classe linear.

Desta forma, conseguimos provar o nosso objetivo. Existem duas constantes positivas c1=4 e c2=5 e um n0=1, tal que c1.n ≤ 4n+1 ≤ c2.n para todos os valores de n maiores ou igual a n0. Portanto, está provado que, de fato, 4n+1 = Θ(n).

Segundo exemplo: uma tentativa frustrada

Vamos tentar demonstrar pela definição que 5n2-n+1 = Θ(n).

Pela definição, tudo o que precisamos fazer é demonstrar que existem duas constantes positivas c1 e c2 e um valor positivo n0 inicial de forma que, para todos os valores de n maiores ou igual a n05n2-n+1 sempre seja maior ou igualc1 multiplicado por n e menor ou igualc2 multiplicado por n (ao mesmo tempo).

Em resumo: precisamos provar que c1.n ≤ 5n2-n+1 ≤ c2.n, para constantes c1 e c2 positivas e um valor n0 inicial positivo.

Para tanto, a primeira decisão que precisamos tomar é escolher valores para as constantes c1 e c2. Neste caso, vamos considerar c1 sendo igual ao valor 5c2 sendo igual ao valor 10. Observe abaixo uma tabela que mostra os resultados da desigualdade para alguns valores de n:

Observe que, para todos os valores de n ≥ 1 expressos na tabela, a função do algoritmo 5n2-n+1 é de fato maior ou igual à função 5n. Contudo, quando o valor de n=3 a função é superada pala função 10n. Acontece que a função 10n, sendo linear, nunca conseguirá superar a função 5n2-n+1, que é quadrática.

Veja no gráfico abaixo o relacionamento entre as funções. Podemos visualizar com maior clareza como a função 5n2-n+1 é limitada inferiormente pela função 5n, para valores de n ≥ 1. Mas perceba que a função 10n não representa um limite assintótico superior, sendo superada pela função 5n2-n+1 para valores de n > 2.

Isso significa que Θ(n) não representa um limite assintótico justo para a função 5n2-n+1. Significa que não existem constantes c1 e c2 positivas e um n0=1, tal que c1.n ≤ 5n2-n+1 ≤ c2.n para todos os valores de n maiores ou igual a n0. Desta forma, está provado que, de fato, 5n2-n+1 ≠ Θ(n). (lê-se “não é téta de n”).

Terceiro exemplo: outra tentativa frustrada

Vamos tentar demonstrar pela definição que 4n+4 = Θ(n2).

Pela definição, tudo o que precisamos fazer é demonstrar que existem duas constantes positivas c1 e c2 e um valor positivo n0 inicial de forma que, para todos os valores de n maiores ou igual a n04n+4 sempre seja maior ou igual c1 multiplicado por n2 e menor ou igualc2 multiplicado por n2 (ao mesmo tempo).

Em resumo: precisamos provar que c1.n2 ≤ 4n+4 ≤ c2.n2, para constantes c1 e c2 positivas e um valor n0 inicial positivo.

Para tanto, a primeira decisão que precisamos tomar é escolher valores para as constantes c1 e c2. Neste caso, vamos considerar c1 sendo igual ao valor 1c2 sendo igual ao valor 3. Observe abaixo uma tabela que mostra os resultados da desigualdade para alguns valores de n:

Observe que, para todos os valores de n ≥ 2 expressos na tabela, a função do algoritmo 4n+4 é de fato menor ou igual à função 3n2. Contudo, quando o valor de n=5 a função é superada pala função n2. Acontece que a função n2, sendo quadrática, nunca conseguirá ser superada pela função 4n+4, que é linear.

Veja no gráfico abaixo o relacionamento entre as funções. Podemos visualizar com maior clareza como a função 4n+4 é limitada superiormente pela função 3n2, para valores de n ≥ 1. Mas perceba que a função n2 não representa um limite assintótico inferior, pois supera a função 4n+4 para n > 4.

Isso significa que Θ(n2) não representa um limite assintótico justo para a função 4n+4. Significa que não existem constantes c1 e c2 positivas e um n0=1, tal que c1.n2 ≤ 4n+4 ≤ c2.n2 para todos os valores de n maiores ou igual a n0. Desta forma, está provado que, de fato, 4n+4 ≠ Θ(n2). (lê-se “não é téta de n ao quadrado”).

Relações entre as notações Big O, Ômega e Theta

Uma maneira fácil e prática de entender a relação entre as três notações assintóticas é determinar os limites assintóticos de uma determinada função por meio da construção do que chamamos de tabela assintótica de relacionamento. Veja como ela pode ser feita.

Dada uma função de complexidade de tempo T(n) = 4n+4, podemos facilmente descobrir todas as suas relações Big O, Ω e Θ construindo uma tabela onde as linhas representam as classes assintóticas e as colunas representam as notações Big O, Ω e Θ.

Perceba que uma função T(n) = 4n+4 somente é Θ(n) (Theta de n) pois é Ω(n) (Ômega de n) e O(n) (Big O de n) ao mesmo tempo. Ou seja, uma função é Theta de uma classe se for Ômega e Big O dessa mesma classe assintótica!

Desta forma, entende-se o significado das notações assintóticas Big O, Ω e Θ. Elas servem para representar limites de desempenho de algoritmos.

Limites rígidos e limites frouxos de algoritmos

Os conceitos de limite rígido e frouxo nos permite classificar o desempenho geral de um algoritmo, levando em consideração o seu melhor e pior caso.

Quando afirmamos que o algoritmo “Bubble Sort” possui:

  • No pior caso: T(n) = 5n2-n+1
  • No melhor caso: T(n) = 3n+2

Estamos afirmando que:

  • No pior caso: T(n) = Θ(n2) (Theta de n ao quadrado), pois possui complexidade quadrática.
  • No melhor caso: T(n) = Θ(n) (Theta de n), pois possui complexidade linear.

Isso significa que o algoritmo “Bubble Sort” possui um limite assintótico frouxo, visto que, no geral, o seu desempenho se comporta de forma distinta para o melhor e pior caso. Ou seja, ele, no geral, é O(n2)Ω(n).

Quando afirmamos que o algoritmo “Find Max” (que calcula o maior valor de um arranjo) possui:

  • No pior caso: T(n) = 4n+1
  • No melhor caso: T(n) = 3n+2

Estamos afirmando que:

  • No pior caso: T(n) = Θ(n)  (Theta de n), pois possui complexidade linear.
  • No melhor caso: T(n) = Θ(n)  (Theta de n), pois possui complexidade linear.

Isso significa que o algoritmo “Find Max” possui um limite assintótico rígido, visto que, no geral, o seu desempenho se comporta da mesma forma para o melhor e pior caso. Ou seja, ele, no geral, é Θ(n).

Exercícios

Tente demonstrar matematicamente que n2+800 = Θ(n2).

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

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

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

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

Preencha a tabela assintótica de relacionamento abaixo:

Nos siga
em nossas redes sociais.

Nos siga em nossas redes sociais.

Deixe um comentário