If you're seeing this message, it means we're having trouble loading external resources on our website.

Se você está atrás de um filtro da Web, certifique-se que os domínios *.kastatic.org e *.kasandbox.org estão desbloqueados.

Conteúdo principal

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, left parenthesis, log, start base, 2, end base, n, right parenthesis, seria incorreto dizer que a busca binária é executada em \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, left parenthesis, 1, right parenthesis. O tempo de execução da busca binária nunca é pior que \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, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis, então para um n suficientemente grande , o tempo de execução é no máximo k, dot, f, left parenthesis, n, right parenthesis para alguma constante k. Veja como pensar em um tempo de execução que é O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis:
6n^2 vs 100n+300
Dizemos que o tempo de execução é "big-O de f, left parenthesis, n, right parenthesis" ou apenas "O de 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, 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, 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, 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, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis em um caso particular, então ele também será 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, left parenthesis, log, start base, 2, end base, n, right parenthesis, ele também é 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, left parenthesis, log, start base, 2, end base, n, right parenthesis, mas não que ela sempre é executada em \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, left parenthesis, n, right parenthesis. Isso porque o tempo de execução não cresce mais rápido do que uma constante vezes 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, 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, left parenthesis, n, squared, right parenthesis, O, left parenthesis, n, cubed, right parenthesis, e O, left parenthesis, 2, start superscript, n, end superscript, right parenthesis. Mas \Theta, left parenthesis, n, right parenthesis, \Theta, left parenthesis, n, squared, right parenthesis, \Theta, left parenthesis, n, cubed, right parenthesis, e \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.

Quer participar da conversa?

Você entende inglês? Clique aqui para ver mais debates na versão em inglês do site da Khan Academy.