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 O (pronuncia-se “bigue ôu”).
Da maneira mais objetiva possível, a notação 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 é 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 linear é igual a T(n)= 4n+1, dizemos que sua complexidade é 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 O.
Exemplo para função linear
Quando dizemos que a função linear 4n+1 é 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, O(n) apresenta-se como um limite superior, e sabemos que a função 4n+1 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 linear (em azul).
Da mesma forma, também é correto afirmar que a função linear 4n+1 é O(n2), pois a função 4n+1 nunca crescerá a ponto de ultrapassar o comportamento quadrático. Portanto, O(n2) também se apresenta como um limite assintótico superior:
Por outro lado, seria errado dizer que a função linear 4n+1 é O(1), pois a função 4n+1 sempre crescerá a ponto de ultrapassar o comportamento constante. Desta forma, O(1) não se apresenta como um limite assintótico superior:
Resumindo:
4n+1 é O(n2), pois pode ser superada (limitada superiormente) por uma função quadrática.
4n+1 é O(n), pois pode ser superada (limitada superiormente) por uma função linear.
4n+1 não é 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 quadrática 5n2-n+1 é 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 5n2-n+1 nunca apresentará um comportamento de crescimento que ultrapasse esse limite superior.
Perceba no gráfico abaixo que: para a função 5n2-n+1, existe uma outra função (em azul) de comportamento quadrático que a limita superiormente:
Da mesma forma, também é correto afirmar que a função quadrática 5n2-n+1 é O(n3), pois a função 5n2-n+1 nunca crescerá a ponto de ultrapassar o comportamento cúbico. Portanto, O(n3) também se apresenta como um limite assintótico superior:
Por outro lado, seria errado dizer que a função 5n2-n+1 é 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 é O(n3), pois pode ser superada (limitada superiormente) por uma função cúbica.
5n2-n+1 é O(n2), pois pode ser superada (limitada superiormente) por uma função quadrática.
5n2-n+1 não é 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 é bigue ôu 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.
Resolução matemática: 1º exemplo
Vamos tentar demonstrar pela definição que 4n+1=O(n) (lê-se “é bigue ôu de n”).
Primeiramente, temos que:
- f(n) = 4n+1
- g(n) = n.
Se, pela definição matemática, precisamos demonstrar que existe uma constante positiva c e um valor positivo n0 inicial, de forma que:
- f(n) ≤ c.g(n) para todos os n ≥ n0.
Então, para este problema, precisamos mostrar que:
- 4n+1 ≤ c.n para todos os n ≥ n0.
Em resumo: precisamos provar que, para todos os valores de n maiores ou igual a n0, a função 4n+1 é menor ou igual a c multiplicado por n.
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 4n+1.
Contudo, o que realmente interessa para a análise de algoritmos é que conseguimos demonstrar o nosso objetivo, ou seja, que existe uma constante c (igual a 5) e um n0 (igual a 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).
Resolução matemática: 2º exemplo
Vamos tentar demonstrar pela definição que 5n2-n+1=O(n2) (lê-se “é bigue ôu de n ao quadrado”).
Primeiramente, temos que:
- f(n) = 5n2-n+1
- g(n) = n2.
Se, pela definição matemática, precisamos demonstrar que existe uma constante positiva c e um valor positivo n0 inicial, de forma que:
- f(n) ≤ c.g(n) para todos os n ≥ n0.
Então, para este problema, precisamos mostrar que:
- 5n2-n+1 ≤ c.n2 para todos os n ≥ n0.
Em suma: precisamos provar que, para todos os valores de n maiores ou igual a n0, a função 5n2-n+1 é menor ou igual a c multiplicado por n2.
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 5n2-n+1.
Contudo, o que realmente interessa para a análise de algoritmos é que conseguimos demonstrar o nosso objetivo, ou seja, que existe uma constante c (igual a 5) e um n0 (igual a 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).
Resolução matemática: 3º exemplo (errado)
Vamos tentar demonstrar pela definição que 2n2-n=O(n).
Primeiramente, temos que:
- f(n) = 2n2-n
- g(n) = n.
Se, pela definição matemática, precisamos demonstrar que existe uma constante positiva c e um valor positivo n0 inicial, de forma que:
- f(n) ≤ c.g(n) para todos os n ≥ n0.
Então, para este problema, precisamos mostrar que:
- 2n2-n ≤ c.n para todos os n ≥ n0.
Em suma: precisamos provar que, para todos os valores de n maiores ou igual a n0, a função 2n2-n é menor ou igual a c multiplicado por n.
À primeira vista, percebe-se que 2n2-n possui comportamento quadrático e c.n possui comportamento linear. Desta forma, percebe-se 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).
No entanto, 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 a torne 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 para diferentes valores da constante c.
Gráfico para a constante c=100
Gráfico para a constante c=1000
Em resumo: não importa quão grande seja a constante c; a função 2n2-n sempre irá superar a função c.n.
Portanto, 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 é bigue ôu de n”).
Exercícios
Para demonstrar que você compreendeu bem o conceito e a definição matemática formal da notação Big O, resolva os exercícios propostos:
Exercícios A
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).
Exercício B
Utilizando a técnica de contagem de instruções, encontre a fórmula de complexidade T(n) do algoritmo abaixo e, em seguida, tente demonstrar matematicamente que essa fórmula encontrada é O(n).
1.public static void func(int[ ] n){
2. for (int i=0; i<n.length-1; i++) {
3. for (int j=0; j<n.length-1; j++) {
4. n[j]=n[j]+i+j;
5. }
6. }
7.}
