Conteúdo principal
Computer science theory
Curso: Computer science theory > Unidade 1
Lição 3: Notação assintóticaNotaçã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 , seria incorreto dizer que a busca binária é executada em em todos os casos. E se encontrarmos o valor procurado no primeiro chute? Então o programa é executado em . O tempo de execução da busca binária nunca é pior que , 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 é , então para um suficientemente grande , o tempo de execução é no máximo para alguma constante . Veja como pensar em um tempo de execução que é :
Dizemos que o tempo de execução é "big-O de " ou apenas "O de ." 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 . Podemos fazer uma afirmação mais forte sobre o tempo de execução no pior caso: ele é . No entanto, se quisermos cobrir todos os casos, a afirmação mais forte que podemos fazer é que a busca binária executa em tempo .
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 é em um caso particular, então ele também será . Por exemplo, podemos dizer que como o pior caso do tempo de execução da busca binária é , ele também é .
O inverso não é necessariamente verdade: como vimos, podemos dizer que a busca binária sempre é executada em , mas não que ela sempre é executada em .
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 . Isso porque o tempo de execução não cresce mais rápido do que uma constante vezes . 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 é um limite superior ao tempo de execução da busca binária. Outros limites superiores imprecisos para a busca binária seriam , , e . Mas , , , e 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?
- A notação big-O dá apenas o limite assintótico superior, e não um limite assintoticamente restrito.(9 votos)