Notação Big-O

Usamos a notação big-Θ para limitar de forma assintótica o crescimento do tempo de execução com fatores constantes acima e abaixo. Algumas vezes, vamos querer limitar somente acima.

Por exemplo, embora o tempo de execução do pior caso da busca binária seja $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis, seria incorreto dizer que a busca binária é executada em $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis em todos os casos. E se encontrarmos o valor procurado no primeiro chute? Então o programa é executado em $\Theta(1)$\Theta, left parenthesis, 1, right parenthesis. O tempo de execução da busca binária nunca é pior que $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis, mas algumas vezes ele é melhor.

Seria conveniente ter uma forma de notação assintótica que diga "o tempo de execução cresce no máximo até um determinado valor, mas poderia crescer mais devagar". A notação "big-O" serve para essas ocasiões.

Se um tempo de execução é $O(f(n))$O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis, então para um $n$n suficientemente grande , o tempo de execução é no máximo $k \cdot f(n)$k, dot, f, left parenthesis, n, right parenthesis para alguma constante $k$k. Veja como pensar em um tempo de execução que é $O(f(n))$O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis:

Dizemos que o tempo de execução é "big-O de $f(n)$f, left parenthesis, n, right parenthesis" ou apenas "O de $f(n)$f, left parenthesis, n, right parenthesis." Usamos a notação big-O para limites assintóticos superiores, uma vez que ela limita o crescimento do tempo de execução superior para valores sufientemente grandes de entrada.

Agora temos uma forma de caracterizar o tempo de execução da busca binária em todos os casos. Podemos dizer que o tempo de execução da busca binária é sempre $O(\log_2 n)$O, left parenthesis, log, start base, 2, end base, n, right parenthesis. Podemos fazer uma afirmação mais forte sobre o tempo de execução no pior caso: ele é $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis. No entanto, se quisermos cobrir todos os casos, a afirmação mais forte que podemos fazer é que a busca binária executa em tempo $O(\log_2 n)$O, left parenthesis, log, start base, 2, end base, n, right parenthesis.

Se você voltar à definição da notação big-Θ, você verá que ela se parece com a notação big-O, exceto que a notação big-Θ limita o tempo de execução superior e inferior, em vez de usar apenas o limite superior. Se dissermos que o tempo de execução é $\Theta(f(n))$\Theta, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis em um caso particular, então ele também será $O(f(n))$O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis. Por exemplo, podemos dizer que como o pior caso do tempo de execução da busca binária é $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis, ele também é $O(\log_2 n)$O, left parenthesis, log, start base, 2, end base, n, right parenthesis.

O inverso não é necessariamente verdade: como vimos, podemos dizer que a busca binária sempre é executada em $O(\log_2 n)$O, left parenthesis, log, start base, 2, end base, n, right parenthesis, mas não que ela sempre é executada em $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis.

Como a notação big-O fornece somente um limite superior assintótico e não um limite assintótico ajustado, podemos fazer afirmações que à primeira vista parecem incorretas, mas estão tecnicamente corretas. Por exemplo, é absolutamente correto dizer que a busca binária é executada em $O(n)$O, left parenthesis, n, right parenthesis. Isso porque o tempo de execução não cresce mais rápido do que uma constante vezes $n$n. Na verdade, cresce mais lentamente.

Pense desta forma. Suponha que você tem 10 reais no seu bolso. Você vai até seu amigo e diz, "Eu tenho uma quantia de dinheiro no meu bolso, e eu garanto que não é mais do que um milhão de reais". Sua declaração é absolutamente verdadeira, porém não muito precisa.

Um milhão de reais é um limite superior a 10 reais, assim como $O(n)$O, left parenthesis, n, right parenthesis é um limite superior ao tempo de execução da busca binária. Outros limites superiores imprecisos para a busca binária seriam $O(n^2)$O, left parenthesis, n, squared, right parenthesis, $O(n^3)$O, left parenthesis, n, cubed, right parenthesis, e $O(2^n)$O, left parenthesis, 2, start superscript, n, end superscript, right parenthesis. Mas $\Theta(n)$\Theta, left parenthesis, n, right parenthesis, $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis, $\Theta(n^3)$\Theta, left parenthesis, n, cubed, right parenthesis, e $\Theta(2^n)$\Theta, left parenthesis, 2, start superscript, n, end superscript, right parenthesis não seriam corretos para descrever o tempo de execução da busca binária em nenhum caso.

Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.