Entendendo algoritmos - Notação Big O

Notação Big O: Medindo a Eficiência dos Algoritmos

A notação Big O representa a velocidade de um algoritmo. No nosso dia a dia, é comum nos depararmos com algoritmos desenvolvidos por outras pessoas e é interessante entender se eles são rápidos ou lentos.

Mas como podemos medir essa velocidade? 🤔

Utilizamos dois algoritmos diferentes para realizar um cálculo e cronometramos o tempo de execução? Na verdade, não. Os tempos de execução crescem com velocidades diferentes.
Vamos usar o exemplo apresentado no livro para ilustrar essa ideia de maneira mais simples.

Exemplo de como o tempo de execução de dois algoritmos pode crescer a taxas diferentes 📈

Jake é um estudante de ciência da computação e está participando de uma competição de algoritmos. Seu primeiro desafio é buscar um número específico em uma lista ordenada de 100 elementos.
Jake precisa decidir qual algoritmo utilizar para a busca. O algoritmo precisa ser rápido e correto, pois ele tem um tempo limitado para resolver o desafio e obter uma boa nota.
Por um lado, a busca binária é mais rápida, mas, por outro lado, a busca simples é mais fácil de implementar.
Vamos considerar que Jake leva 1 milissegundo para verificar um elemento. Se ele usar a busca simples, levaria 100 milissegundos para executar o algoritmo, pois ele teria que verificar os 100 elementos. No entanto, se ele usar a busca binária, ele verificará apenas 7 elementos, pois log de 100 na base 2 é aproximadamente 7.
Agora, imagine se a lista crescer ainda mais. Se Jake precisar verificar mais de 1 milhão de elementos, utilizando a busca binária, seriam necessários cerca de 20 milissegundos para executar o algoritmo. Já utilizando a busca simples, seriam necessários 1 milhão de milissegundos, o que equivale a aproximadamente 16 minutos.
Podemos perceber que o tempo de execução não é algo fixo e independente do tamanho dos elementos com os quais estamos trabalhando. O ponto que queremos destacar é que o tempo de execução da busca simples e da busca binária cresce de acordo com suas taxas. Conforme o número de elementos a serem verificados aumenta, a busca binária aumenta apenas um pouco o tempo de execução, enquanto a busca simples aumenta consideravelmente muito mais.
Um exemplo do tempo de execução variando de acordo com a taxa →

Desse modo, entendemos que não basta sabermos quanto tempo um algoritmo demora para ser executado e sim o tempo que leva para ser executado conforme sua taxa aumenta. Portanto, aí que entra a famosa Notação Big O

Vamos supor que temos uma lista de tamanho (n). O tempo de execução na notação Big o é
$O(n)$
A notação não nos fornece o tempo de execução em segundos, mas sim o quão rapidamente o algoritmo cresce. Sendo assim, podemos escrever a notação Big O da seguinte forma:

Esse formato nos mostra o número de operações que um algoritmo realiza. Chamamos de Big O porque colocamos um 'O' maiúsculo na frente do número de operações 🤭
Portanto, podemos definir o tempo de execução de um algoritmo de busca simples como O(n) e o tempo de execução de um algoritmo de busca binária como O(log n), e assim por diante, dependendo do algoritmo que estamos utilizando.

A espera do pior cenário ☠️

Na notação Big O, estabelecemos o tempo de execução para o pior cenário do problema que estamos resolvendo. Por exemplo, para a busca simples, o tempo de execução é O(n), o que significa que, no pior caso, teríamos que verificar todos os 'n' elementos da lista. Se ocorrer de encontrar o elemento que preciso na minha primeira busca, podemos acabar pensando que o algoritmo teve um tempo de O(1), mas na verdade não. Sempre levamos em consideração a pior hipótese, onde analisamos cada item da lista, esse é o tempo de O(n).
💡 No entanto, é importante destacar que podemos analisar não apenas o pior caso, mas também o caso médio.

Precisamos entender que tudo isso é uma simplificação. Não podemos determinar exatamente o tempo de execução na notação Big O em termos de número de operações, mas a aproximação já nos ajuda bastante.
Até agora, discutimos apenas dois algoritmos: busca binária e busca simples. No entanto, existem muitos outros tipos de algoritmos, cada um adequado para diferentes contextos e usos. Por exemplo, a busca binária não pode ser usada como uma solução universal, pois é necessário analisar e identificar qual algoritmo utilizar em cada caso específico

Conclusão

Espero que tenha gostado do artigo e estou aberto a dúvidas e correções também 🤘
Escrevi um artigo anterior a esse sobre pesquisa simples e pesquisa binária caso queira dar uma olhada.

Referências

Conteúdo desse artigo foi retirado do livro "Entendendo algoritmos - Um guia ilustrado para programadores e outros curiosos". Capítulo sobre Notação Big O a partir da página 29.