Notação Big

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 ). A notação , quando aplicada a um algoritmo, nos fornece um limite superior para o tempo de execução desse algoritmo.

No nosso exemplo da seção anterior, poderíamos dizer que o algoritmo_a possui complexidade , e o algoritmo_b possui complexidade . Mas o que isso quer dizer exatamente?

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

Gráfico ilustrando a notação O.

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

Definição: Dizer que significa que existe constante positiva tal que , para algum maior que . O ponto é o ponto no gráfico acima em que a curva da função intercepta a curva da função .

No nosso exemplo anterior, podemos dizer que o algoritmo_a é porque, dado que sabemos que ele executa cerca de operações, podemos escolher uma constante positiva , de modo que sempre será maior que . O mesmo raciocínio pode ser aplicado ao algoritmo_b para concluir que ele possui complexidade .

Ao analisar o gráfico acima, vemos que a função cresce mais rapidamente que , pois a curva de está acima da de , a partir de um dado valor de . Quando isso acontece, costumamos dizer que domina assintoticamente , ou que é assintoticamente superior a . Matematicamente esta afirmação nos diz que .

Uma outra forma de entender a notação é em termos de comparações. Se uma função é , podemos dizer que .

Além de comparações com menor que e maior que, a notaçã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:

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

A funçã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 , que pode ser definida assim:

Definição: Dizer que significa que existe constante positiva tal que .

Além disso, se uma função satisfaz tanto e , então dizemos que (leia-se: “theta”). A função 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 , , e correspondem, grosso modo, a , , e . Existem também funções que correspondem a e , são elas: e , 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 1: Para cada uma das afirmações abaixo, julgue se ela é verdadeira ou falsa.

Resposta: Verdadeiro. Como não consideramos constantes ao analisar a complexidade assintótica de um algoritmo, podemos eliminar o termo , e com isso concluímos que a complexidade do algoritmo é .

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

Resposta: Verdadeiro. Como a função cresce mais lentamente que a função , podemos dizer que é um limite superior para , e portanto é . Entretanto, dizemos que não é um limite superior firme, no sentido de que as funções e 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 é é que ela é .

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


Exercício 2: Para cada uma das funções abaixo, diga qual é o limite assintótico superior (notação ) que a representa.

Resposta: , pois esconsideramos constantes quando estamos fazendo análise assintótica de complexidade.

Resposta: , pois desconsideramos constantes e termos de ordem menor ao fazer análise assintótica de complexidade.

Resposta: , pelo mesmo raciocício dos itens anteriores.

Resposta: , pelo mesmo raciocício dos itens anteriores.