Notação Big $O$

Na seção anterior, explicamos brevemente como determinar aproximadamente o número de operações que um algoritmo executa. O processo foi um pouco trabalhoso porque queríamos ilustrar como as coisas funcionam quando não possuímos ferramental teórico nenhum. Entretanto, com um pouco de prática e com as ferramentas certas, fica muito mais fácil analisar a complexidade assintótica de algoritmos. Nesta seção, explicaremos a principal ferramenta usada em análise de complexidade e incluiremos alguns exercícios para que você pratique os conceitos aprendidos.

A principal ferramenta usada para se analisar a complexidade assintótica de algoritmos é chamada notação big-oh (ou simplesmente notação $O$). A notação $O$, quando aplicada a um algoritmo, nos fornece um limite superior para o tempo de execução desse algoritmo. A notação big-oh é uma notação universal para se falar de desempenho de algoritmos.

No nosso exemplo da seção anterior, poderíamos dizer que o algoritmo_a possui complexidade $O(n^2)$, e o algoritmo_b possui complexidade $O(n)$. Mas o que isso quer dizer exatamente?

Ao dizer que um algoritmo é $O(n)$, estamos dizendo que existe uma constante positiva $c$ pela qual podemos multiplicar $n$, e esta nova função $g(n) = c \times n$ é um limite superior para o tempo de execução do algoritmo em questão. Graficamente, temos a seguinte situação:

Big-Oh

Pelo gráfico, podemos chegar a uma definição mais formal da função $O$:

Definição: Dizer que $f(n) = O(g(n))$ significa que existe constante positiva $c$ tal que $f(n) \leq c \times g(n)$, para algum $n$ maior que $n_{0}$. O ponto $n_{0}$ é o ponto no gráfico acima em que a curva da função $f(n)$ intercepta a curva da função $g(n)$.

No nosso exemplo anterior, podemos dizer que o algoritmo_a é $O(n)$ porque, dado que sabemos que ele executa cerca de $n$ operações, podemos escolher uma constante positiva $c = 2$, de modo que $g(n) = c \times n$ sempre será maior que $f(n) = n$. O mesmo raciocínio pode ser aplicado ao algoritmo_b para concluir que ele possui complexidade $O(n^2)$.

Ao analisar o gráfico acima, vemos que a função $g(n)$ cresce mais rapidamente que $f(n)$, pois a curva de $g(n)$ está acima da de $f(n)$, a partir de um dado valor de $n$. Quando isso acontece, costumamos dizer que $g(n)$ domina assintoticamente $f(n)$, ou que $g(n)$ é assintoticamente superior a $f(n)$. Matematicamente esta afirmação nos diz que $\lim_{n\to\infty} \frac{g(n)}{f(n)} = \infty$.

Uma outra forma de entender a notação $O$ é em termos de comparações. Se uma função $f(n)$ é $O(g(n))$, podemos dizer que $f(n) \leq g(n)$.

Além de comparações com menor que e maior que, a notação $O$ nos permite realizar operações matemáticas entre duas funções de complexidade. As operações mais comuns a serem realizadas são a soma e a multiplicação:

  • Soma: $O(f(n)) + O(g(n)) = O(max(f(n), g(n))).$

  • Multiplicação: $O(f(n)) * O(g(n)) = O(f(n) * g(n)).$

As regras acima não podem ser estendidas para subtração e divisão.

A função $O$ é usada quando desejamos encontrar o limite superior do tempo de execução de um algoritmo. Entretanto, em algumas situações, isso não é o suficiente. Existem situações em que precisamos dizer qual o limite inferior do tempo de execução de um algoritmo. Para isso, usamos a função Ômega, representada por $\Omega$, que pode ser definida assim:

Definição: Dizer que $f(n) = \Omega(g(n))$ significa que existe constante positiva $c$ tal que $g(n) \leq c \times f(n)$.

Além disso, se uma função $f(n)$ satisfaz tanto $f(n) = O(g(n))$ e $f(n) = \Omega(g(n))$, então dizemos que $f(n) = \Theta(g(n))$ (leia-se: "theta"). A função $\Theta$ nos fornece um limite inferior e superior, ou seja, um limite mais firme e preciso, para o tempo de execução de um algoritmo.

As funções $O$, $\Theta$, e $\Omega$ correspondem, grosso modo, a $\leq$, $=$, e $\geq$. Existem também funções que correspondem a $<$ e $>$, são elas: $o$ e $\omega$, respectivamente. Essas funções, entretanto, não são muito usadas na prática e por isso quase não falaremos sobre elas durante este curso.

Exercícios

Exercício

Para cada uma das afirmações abaixo, julgue se ela é verdadeira ou falsa.

  • $f(n) = 10^6 \times n$ é $O(n)$?

Clique para ver a solução

Verdadeiro. Como não consideramos constantes ao analisar a complexidade assintótica de um algoritmo, podemos eliminar o termo $10 ^6$, e com isso concluímos que a complexidade do algoritmo é $O(n)$.


  • $f(n) = 1.000 \times n$ é $O(n^2)$?

Clique para ver a solução

Verdadeiro. Existe uma nuance neste item que é importante discutirmos. Tecnicamente, se uma função $f(n)$ é $O(n)$, então ela também é $O(n^2)$, $O(n^3)$, $O(n^4)$, $O(2^n)$, $O(n!)$, e assim por diante, pois todas essas funções são um limite superior para a função $f(n)$. Entretanto, na prática, quando usamos a notação $O$, tentamos encontrar um limite superior mais próximo possível (ou também conhecido como limite superior mais firme). Então, apesar de $f(n) = 1.000 \times n$ ser $O(n^2)$, em uma situação real, seria mais preciso dizermos que $f(n) = 1.000 \times n$ é $O(n)$.


  • $f(n) = 10^4 \times log(n)$ é $O(n)$?

Clique para ver a solução

Verdadeiro. Como a função $log(n)$ cresce mais lentamente que a função $n$, podemos dizer que $n$ é um limite superior para $log(n)$, e portanto $log(n)$ é $O(n)$. Entretanto, dizemos que $n$ não é um limite superior firme, no sentido de que as funções $log(n)$ e $n$ não diferem somente por uma constante, como mencionamos anteriormente. Sempre que possível, desejamos prover um limite assintótico firme em nossas análises. Assim, podemos dizer que um limite assintótico firme para a função $f(n) = 10^4 \times log(n)$ é $O(n)$ é que ela é $O(log(n))$.


  • $f(n) = 10^9 \times log(n)$ é $O(log(n))$?

Clique para ver a solução

Verdadeiro. O raciocínio é o mesmo do primeiro item.


  • $T(n) = 2^{n + 10}$ é $O(2^n)$

Clique para ver a solução

Verdadeiro. $2^{n + 10} = 2^{10} * 2^n = 1024 * 2^n$. Como na notação big-oh descartamos constantes, podemos concluir que $T(n) = 2^{n + 10}$ é $O(2^n)$.


  • $T(n) = 2^{10n}$ é $O(2^n)$

Clique para ver a solução

Falso. Se $2^{10n}$ fosse $O(2^n)$, existiria uma constante $c$ tal que $2^{10n} \leq c \times 2^n$. Porém, se dividirmos os dois lados da equação $2^{10n} \leq c \times 2^n$ por $2^n$, teremos $2^{9n} \leq c$, o que é claramente falso.


Exercício

Para cada uma das funções abaixo, diga qual é o limite assintótico superior (notação $O$) que a representa.

  • $f(n) = 2 \times n + 10.000$.

Clique para ver a solução

$O(n)$, pois esconsideramos constantes quando estamos fazendo análise assintótica de complexidade.


  • $f(n) = n^2 + 10.000 \times n + 20$.

Clique para ver a solução

$O(n^2)$, pois desconsideramos constantes e termos de ordem menor ao fazer análise assintótica de complexidade.


  • $f(n) = 2^n + 5 \times n^6$.

Clique para ver a solução

$O(2^n)$, pelo mesmo raciocício dos itens anteriores.


  • $f(n) = 50 \times n \times log(n)$.

Clique para ver a solução

$O(n \times log(n))$, pelo mesmo raciocício dos itens anteriores.


Playground

# Use este espaço para praticar o que você aprendeu nesta seção. # Basta digitar o código no espaço abaixo e clicar 'run'.