Usamos a notação big-Θ para delimitar asintóticamente o crescimento do tempo de execução dentro dos fatores constantes superiores e inferiores. Algumas vezes queremos saber apenas o limite superior. Por exemplo, embora o tempo de execução no pior caso da busca binária é Θ(lgn) \Theta(\lg n) , estaria incorreto dizer que a busca binária executa em um tempo Θ(lgn) \Theta(\lg n) em todos os casos. E se encontrarmos o valor alvo na primeira tentativa? Então ele executa em um tempo Θ(1) \Theta(1) . O tempo de execução da busca binária nunca é pior do que Θ(lgn) \Theta(\lg n) , mas algumas vezes pode ser melhor. Seria conveniente ter uma forma de notação assintótica que diga "o tempo de execução cresce no máximo assim, mas poderia crescer mais devagar". A notação "O-grande" serve para tais ocasiões.
Se um tempo de execução é O(f(n)) O(f(n)) , então para um n n suficientemente grande , o tempo de execução é no máximo kf(n) k \cdot f(n) para alguma constante k k . Veja como pensar em um tempo de execução que é O(f(n)) O(f(n)) :
Dizemos que o tempo de execução é "big-O de f(n) f(n) " ou apenas "O de f(n) f(n) ." 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 maneira 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(lgn) O(\lg n) . Podemos afirmar algo mais forte sobre o tempo de execução no pior caso: ele é Θ(lgn) \Theta(\lg n) . No entanto, se quisermos cobrir todos os casos, a afirmação mais estrita que podemos fazer é que a busca binária executa em tempo O(lgn) O(\lg n) .
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, ao invés de apenas superior. Se dizemos que o tempo de execução é Θ(f(n)) \Theta(f(n)) em um caso particular, então ele também é O(f(n)) O(f(n)) . Por exemplo, podemos dizer que porque o pior caso do tempo de execução da busca binária é Θ(lgn) \Theta(\lg n) , ele também é O(lgn) O(\lg n) . O inverso não é necessariamente verdade: como vimos, podemos dizer que a busca binária sempre executa em um tempo O(lgn) O(\lg n) mas não que ela sempre executa em um tempo Θ(lgn) \Theta(\lg n) .
Porque a notação big-O dá apenas o limite assintótico superior, e não um limite assintoticamente restrito, podemos fazer afirmações que a primeira vista parecem incorretas, mas tecnicamente estão corretas. Por exemplo, é absolutamente correto dizer que a busca binária executa em um tempo O(n) O(n) . Isto é porque o tempo de execução não cresce mais rápido do que uma constante vezes n n . De fato, ele cresce mais lentamente. Pense nisso desta forma. Suponha que você tem 10 reais em sua carteira. Você vai até seu amigo e diz, "Eu tenho uma quantidade de dinheiro em minha carteira, e eu garanto que não é mais do que um milhão de reais". Sua afirmação está absolutamente correta, embora não muito precisa. Um milhão de reais é um limite superior para 10 reais, assim como O(n) O(n) é um limite superior para o tempo de execução da busca binária. Outros limites superiores imprecisos da busca binária poderiam ser O(n2) O(n^2) , O(n3) O(n^3) , e O(2n) O(2^n) . Mas nenhum destes Θ(n) \Theta(n) , Θ(n2) \Theta(n^2) , Θ(n3) \Theta(n^3) , e Θ(2n) \Theta(2^n) estariam corretos para descrever o tempo de execução da busca binária em qualquer 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.
Carregando