Data: 28/02/2003
Redatora: Camila Ribeiro Rocha

Tópicos:

1. Notação Θ
2. Notação O
3. Notação Ω
4. Notação assintótica em igualdades
5. Notação o
6. Notação ω
7. Comparação de funções
8. Novidades da Seção 3.2: Notações padrão e funções comuns

Notação Θ

Uma função f(n) é Θ(g(n)) se existem constantes positivas c₁ e c₂ tal que, multiplicadas por g(n), c₁g(n) e c₂g(n) limitem f(n) acima e abaixo, para um valor a partir de um determinado n_o.

Segundo o prof. Meidanis, a expressão f(n) = Θ(g(n)) significa que as funções f(n) e g(n) possuem a mesma ordem de crescimento, isto é, crescem de forma equiparável. As funções n² e 5n², por exemplo, crescem em ritmo quadrático.

Notação O

Quando uma função f(n) é O(g(n)), a função g(n) impõe a f(n) um limite assintótico superior. Ou seja, multiplicada por uma constante c, a função g(n) limita superiormente a função f(n), a partir de um determinado  n_o.

A expressão f(n) = O(g(n)) significa que f(n) não cresce mais que g(n), podendo crescer de forma igual ou inferior.

Quando questionado sobre a relação da notação O com o pior caso de um algoritmo, o prof. Meidanis respondeu que essa é a notação mais utilizada na análise de complexidade de algoritmos em geral, normalmente para pior caso (entretanto, há casos como o QuickSort, por exemplo, que a notação O também é utilizada para o caso médio). As outras são raramente utilizadas: a notação Ω é usada algumas vezes para definição de limites inferiores. Porém, é importante lembrar que as definições de notações são independentes da análise de algoritmos, podendo ser utilizados para outros fins.

Notação Ω

A notação Ω é similar à notação O: uma função f(n) é Ω(g(n)) quando a função g(n) impõe a f(n) um limite assintótico inferior, que significa que, sendo a função g(n) multiplicada por uma constante c, a função f(n) nunca será inferior a c g(n), a partir de um determinado n_o.

A expressão f(n) = Ω(g(n)) significa que a ordem de crescimento de f(n) é maior ou igual à ordem de g(n).

Notação assintótica em igualdades

Ao estar presente em uma equação, um elemento de notação assintótica não deve ser interpretado como um componente normal da equação, e sim como um elemento de complexidade. 

Porém, há diferentes significados para a presença da notação assintótica na equação. Se estiver do lado direito da igualdade e fizer parte de uma expressão, ela é interpretada como alguma função anônima de determinada ordem de grandeza, eliminando detalhes não essenciais. Por exemplo, a recorrência T(n) = 2T(n/2) + Θ(n) pode ser interpretada como T(n) = 2T(n/2) + f(n), sendo a função f(n) uma função particular de ordem de crescimento n. A notação Θ aparece para eliminar detalhes da equação.

Outro exemplo de utilização no lado direito: ∑ⁿ_i=1  O(i)
Para essa equação, pode-se chegar a várias interpretações diferentes. Porém, a interpretação correta é que trata-se de um somatório de tamanho n de uma única função f(n), de ordem de crescimento n.

Quando a notação encontra-se sozinha do lado esquerdo da igualdade, a notação exprime a ordem de crescimento de toda a equação, como representado nas seções sobre as notações Θ, O e Ω.

Na análise de algoritmos, essa substituição das funções pela notação é utilizada para eliminar detalhes da equação que não influenciam no resultado final da análise (como as constantes), sendo o resultado final a ordem de crescimento da equação.

Notação o

Assim como a notação O, a notação o também denota um limite assintótico superior. Porém, quando f(n) é o(g(n)), para qualquer constante c > 0 que multiplique g(n) existe um n₀ tal que para todo n ≥ n_o, o valor f(n) é menor que c g(n). Ou seja, se f(n) = O(g(n)), a ordem de crescimento de f(n) nunca será maior que a de g(n), podendo ser igual. Entretanto, se f(n) = o(g(n)), a ordem de crescimento de f(n) nunca será maior nem igual à de g(n).

Observando os limites das notações O e o, é possivel perceber a diferença das duas notações. Na notação o, à medida que n se aproxima do ∞, f(n) se torna insignificante em relação à g(n):

lim    f(n) = 0, isto é, g(n) cresce muito mais que f(n).
^n->∞ g(n)

Já com notação O, a medida que se aproxima do ∞, não necessariamente f(n) se tornará insignificante em relação a g(n):

lim    f(n) = 0 ou lim    f(n) = c, isto é, g(n) cresce mais ou igualmente que f(n).
^n->∞ g(n)              ^n->∞ g(n)

A notação o oferece uma análise menos exata que a notação O, por isso geralmente não é utilizada em análise de algoritmos. Um exemplo dessa deficiência é a comparação abaixo:

• A igualdade f(n) = O(n²) é interpretada como sendo f(n) uma função de ordem no máximo quadrática.
• A igualdade f(n) = 3n² + O(n) é mais exata que a anterior, e significa que, além do termo de ordem n², a função também possui termos de ordem n ou menor.
• Já na igualdade f(n) = 3n² + o(n²), sabe-se que f(n) possui o termo de ordem n² mais outros termos que são menores que n² (podendo ser valores como n^1,5, por exemplo). Portanto, a notação O oferece uma análise mais exata que a notação o.

Para análise de algoritmos, as notações mais utilizadas são O (para um limite superior) e Θ (para um limite exato). As notações o e ω são raramente utilizadas.

Notação ω

A notação ω denota um limite assintótico inferior, assim como Ω. A diferença é que, se f(n) = ω(g(n)), para qualquer constante c > 0 que multiplique g(n) existe um n₀ > 0 tal que para todo n ≥ n_o, f(n) nunca será menor nem igual a g(n). Assim, diferentemente de Ω, o crescimento da função f(n) nunca se igualará ao de g(n).

Comparação de funções

Foram abordados aspectos sobre as regras de transitividade e a analogia com a comparação de números reais. Para a demonstração da regra de transitividade, foi utilizado o gráfico:

• f(n) = O(g(n)) ≈  a ≤ b,
• f(n) = Ω(g(n))  ≈  a ≥ b,
• f(n) = Θ(g(n))  ≈  a = b,
• f(n) = o(g(n))  ≈  a < b,
• f(n) = ω(g(n))  ≈  a > b.

Novidades da Seção 3.2: Notações padrão e funções comuns

Esta seção do livro revê funções e notações matemáticas padrão e explora os relacionamentos entre elas. Como a maioria dos assuntos já foi estudado anteriormente, apenas aqueles que eram novidades foram abordados pelo prof. Meidanis, e serão relatados.

• Iteração Funcional: a notação f⁽ⁱ⁾(n) denota a aplicação da função f(n) iterativamente i vezes a um valor inicial n.
  
  
• Piso e Teto: Piso(x) refere-se ao maior inteiro menor ou igual a x, enquanto teto (x) refere-se ao menor inteiro maior ou igual a x.
  
  
• Monotonicidade: classificação de funções em:
  • (Monotonicamente) Crescente: se m ≤ n, f(m) ≤ f(n)
  • (Monotonicamente) Decrescente: se m ≤ n, f(m) ≥ f(n)
  • Estritamente Crescente: se m < n, f(m) < f(n)
  • Estritamente Decrescente: se m < n, f(m) > f(n)
    
    
• Aproximação de Stirling: fórmula para cálculo de fatorial:
        n! =  √ (2∏n) * (n/e)ⁿ * (1 + Θ(1/n)), onde e é a base do logaritmo natural.
  O prof. Meidanis lembrou que outra forma para o cálculo do fatorial é a função gama, criada por Euler.
  
  
• Razão áurea (Ф): razão áurea é um número irracional em forma de símbolo, como o ∏.
  Seu valor é (1 +  √(5))/2. Segundo o prof. Meidanis, os artistas do Renascimento consideravam a razão áurea como uma proporção perfeita.
  A razão áurea e o seu conjugado (^Ф) são utilizados na fórmula para o cálculo dos números de Fibonacci:
  F_i = Фⁱ - ^Фⁱ
         √(5)

• Bases de logaritmo: logaritmos com base > 1 são todos Θ um do outro, ou seja, tem a mesma ordem de grandeza e diferem apenas por uma constante. Assim, para o cálculo de complexidade, qualquer base é válida (sendo a mais utilizada a base 2, pois muitos algoritmos dividem o problema em 2 recursivamente).