fbpx

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.

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 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.
notação-big-o-06
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:
notação-big-o-05

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:

notação-big-o-04

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:

notação-big-o-01

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:

notação-big-o-02

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:

notação-big-o-03

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:

análise-de-algoritmos-04

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:

análise-de-algoritmos-05

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:

análise-de-algoritmos-01

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
análise-de-algoritmos-06
Gráfico para a constante c=100
análise-de-algoritmos-02
Gráfico para a constante c=1000
análise-de-algoritmos-03

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

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