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

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

Introdução à notação Big O

No último artigo conhecemos as classes assintóticas e vimos como elas são importantes para a análise de algoritmos. Neste artigo veremos a primeira de três notações usadas na computação para representar o comportamento assintótico dos algoritmos: a notação Big O (pronuncia-se “bigue ôu”).

Se você ainda não leu o artigo sobre classes assintóticas, clique neste link e acesse o artigo onde te ensinamos conhecimentos valiosos sobre o assunto.

Da maneira mais objetiva possível, a notação Big O nos fornece uma simbologia simplificada para representar um limite superior de desempenho para um algoritmo. Um limite máximo de tempo que um algoritmo leva para ser executado.

  • Ao invés de dizer que a complexidade de tempo do algoritmo Bubble Sort (no pior caso) é igual a T(n)= 5n2-n+1​, dizemos que sua complexidade é Big O(n2​) (lê-se “bigue ôu de n ao quadrado”). Usamos a classe quadrática n2 dentro dos parênteses da notação para especificar que o algoritmo leva, no máximo, um tempo quadrático para ser executado.
  • Ao invés de dizer que a complexidade de tempo do algoritmo que encontra o maior valor de um arranjo (no pior caso) é igual a T(n)= 4n+1​, dizemos que sua complexidade é Big O(n​) (lê-se “bigue ôu de n”). Usamos a classe linear n​ dentro dos parênteses da notação para especificar que o algoritmo leva, no máximo, um tempo linear para ser executado.

Essa é uma explicação um pouco rasteira, mas serve de introdução para você começar a compreender o significado e o uso da notação Big O.

Exemplo para função linear

Quando dizemos que a função 4n+1 é Big O(n), estamos afirmando que o comportamento assintótico de uma função linear é igual ou superior ao dela. Significa dizer: a função 4n+1 nunca crescerá a ponto de ultrapassar o comportamento linear. Desta forma, Big O(n) apresenta-se como um limite superior, e sabemos que a função nunca apresentará um comportamento de crescimento que ultrapasse esse limite superior. Exemplo: para a função 4n+1, existe uma outra função de comportamento linear que a limita superiormente. Perceba no gráfico abaixo que, para valores de n>1, a função 4n+1 é superada por uma outra função da classe n.
Da mesma forma, também é correto afirmar que 4n+1 é Big O(n2​), pois a função 4n+1 nunca crescerá a ponto de ultrapassar o comportamento quadrático. Desta forma, O(n2​) também se apresenta como um limite assintótico superior:

Agora, seria errado dizer que 4n+1 é Big O(1), pois a função 4n+1 sempre crescerá a ponto de ultrapassar o comportamento constante. Desta forma, Big O(1) não se apresenta como um limite assintótico superior:

Resumindo:

4n+1 é Big O(n2​), pois pode ser superada (limitada superiormente) por uma função quadrática.

4n+1 é Big O(n), pois pode ser superada (limitada superiormente) por uma função linear.

4n+1 não é Big O(1), pois não pode ser superada (limitada superiormente) por uma função constante.

Exemplo para função quadrática

Quando dizemos que a função 5n2​-n+1 é Big O(n2​), estamos afirmando que o comportamento assintótico de uma função quadrática é igual ou superior ao dela. Significa dizer: a função 5n2​-n+1 nunca crescerá a ponto de ultrapassar o comportamento quadrático. Desta forma, O(n2​) apresenta-se como um limite superior e sabemos que a função nunca apresentará um comportamento de crescimento que ultrapasse esse limite superior.

Exemplo: para a função 5n2​-n+1, existe uma outra função de comportamento quadrático que a limita superiormente. Veja abaixo:

Da mesma forma, também é correto afirmar que 5n2​-n+1 é Big O(n3​), pois a função 5n2​-n+1 nunca crescerá a ponto de ultrapassar o comportamento cúbico. Desta forma, O(n3) também se apresenta como um limite assintótico superior:

Agora, seria errado dizer que 5n2​-n+1 é Big O(n), pois a função 5n2​-n+1 sempre crescerá a ponto de ultrapassar o comportamento linear. Desta forma, O(n) não se apresenta como um limite assintótico superior:

Resumindo:

5n2​-n+1 é Big O(n3​), pois pode ser superada (limitada superiormente) por uma função cúbica.

5n2​-n+1 é Big O(n2​), pois pode ser superada (limitada superiormente) por uma função quadrática.

5n2​-n+1 não é Big O(n​), pois não pode ser superada (limitada superiormente) por uma função linear.

Definição matemática formal da Notação Big O

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) = O(g(n)) (lê-se “f de n é Big O 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 O

Vamos tentar demonstrar pela definição que 4n+1=O(n) (lê-se “é Big O 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 n0, 4n+1 sempre seja menor 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 5. Observe abaixo uma tabela que mostra os resultados da desigualdade para c=5 e para alguns valores de n:

Observe que para n igual a 0(zero) a função do algoritmo 4n+1 é maior que c.n. Mas quando n é igual a 1 os valores de c.n começam a superar a função do algoritmo 4n+1. Quando plotamos um gráfico para ambas as funções, visualizamos com maior clareza esse exato momento de superação da função c.n:

Isso significa que O(n) representa um limite assintótico superior para a função 4n+1. Pois, a partir de um determinado valor n, c.n supera a função.

Contudo, o que realmente interessa para a análise de algoritmos é que conseguimos demonstrar o nosso objetivo, ou seja, que existe uma constante c=5 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=O(n) (é Big O de n).

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

Vamos tentar demonstrar pela definição que 5n2-n+1=O(n2) (lê-se “é Big O 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 n0​, 5n2-n+1 sempre seja menor ou igual a c multiplicado por n2.

Em resumo, precisamos provar que 5n2-n+1 ≤ 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 5. Observe abaixo uma tabela que mostra os resultados da desigualdade para c=5 e para alguns valores de n:

Observe que para n igual a 0(zero) a função do algoritmo 5n2-n+1 é maior que c.n2. Mas quando n é igual a 1 os valores de c.n2 começam a superar a função do algoritmo 5n2-n+1. Quando plotamos um gráfico para ambas as funções, visualizamos com maior clareza esse exato momento de superação da função c.n2:

Isso significa que O(n2) representa um limite assintótico superior para a função 5n2-n+1. Pois, a partir de um determinado valor n, c.n2 supera a função.

Contudo, o que realmente interessa para a análise de algoritmos é que conseguimos demonstrar o nosso objetivo, ou seja, que existe uma constante c=5 e um n0=1, tal que 5n2-n+1 ≤ c.n2 para todos os valores de n maiores ou igual a n0. Desta forma, está provado que, de fato, 5n2-n+1=O(n2) (é Big O de n ao quadrado).

Terceiro exemplo: uma tentativa frustrada

Vamos tentar demonstrar pela definição que 2n2-n=O(n).

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 maiores que n0, 2n2-n sempre seja menor ou igual a c multiplicado por n.

Em resumo, precisamos provar que 2n2-n≤c.n, para uma constante c e um valor n0 inicial.

À primeira vista, percebe-se que 2n2-n possui comportamento quadrático e c.n possui comportamento linear. Por isso somos tentados a afirmar que essa demonstração é falsa, pois uma função linear (c.n) não pode representar um limite assintótico superior para uma função quadrática (2n2-n). 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 valor de n sempre irá superá-lo.

Abaixo são exibidos alguns gráficos que ilustram alguns cenários de c.n sendo superada pela função quadrática 2n2-n:

Gráfico para a constante c=10
Gráfico para a constante c=100
Gráfico para a constante c=1000

Ou seja, não importa o quão grande seja a constante c. A função 2n2-n sempre irá superar a função c.n.

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

Exercícios

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

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

Tente demonstrar matematicamente que n2=O(n).

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

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

Compartilhe este artigo

Share on whatsapp
WhatsApp
Share on facebook
Facebook
Share on twitter
Twitter
Share on linkedin
LinkedIn
Share on email
Email

Nos siga
em nossas redes sociais.