Artigo original: Big O Notation Explained with Examples
A notação Big O é uma forma de descrever a velocidade ou a complexidade de um determinado algoritmo. Se o seu projeto atual exige um algoritmo pré-definido, é importante entender se ele é mais rápido ou mais lento em comparação com outras opções.
O que é a notação Big O e como ela funciona?
De modo simplificado, a notação Big O informa a você o número de operações que um algoritmo fará. Ele recebe o nome do literal "Big O" adiante de um número de operações estimado.
O que a notação Big O não diz a você é a velocidade do algoritmo em segundos. Há muitos fatores que influenciam o tempo que leva para a execução de um algoritmo. Em vez disso, usamos a notação Big O para comparar algoritmos diferentes pelo número de operações que ele realiza.
A Big O estabelece o pior caso para o tempo de execução
Imagine que você é um professor e tem uma aluna chamada Jane. Você quer encontrar os registros dela. Você usa um algoritmo de busca simples para percorrer o banco de dados da escola do bairro.
Você saber que uma busca simples leva O(n) vezes para ser executada. Isso quer dizer que, no pior caso, você terá que examinar cada registro (representado aqui pelo n) até encontrar o de Jane.
Quando você executa uma busca simples, no entanto, descobre que o registro de Jane é o primeiro do banco de dados. Você não precisa olhar todas as outras entradas – já a encontrou na primeira tentativa.
Esse algoritmo levou O(n) vezes? Ou levou O(1) vez, já que você encontrou o registro de Jane de primeira?
Neste caso, 0(1) é o melhor cenário – você teve a sorte de achar o registro de Jane bem no começo. Mas a notação Big O leva em conta o pior dos casos, que é 0(n) para a busca simples. É uma reafirmação de que a busca simples nunca será mais lenta que O(n).
O número de vezes de execução de um algoritmo cresce em taxas diferentes
Leve em conta que é preciso 1 milissegundo para verificar cada elemento no banco de dados a escola do bairro.
Com a busca simples, se você tivesse de verificar 10 entradas, a execução levaria 10 ms. Com o algoritmo de busca binária, porém, é necessário verificar apenas 3 elementos, o que faz com que a execução leve 3 ms.
Na maioria dos casos, a lista ou banco de dados em que você precisa procurar registros terá centenas ou milhares de elementos.
Se houver 1 bilhão de elementos, usar uma busca simples levará 1 bilhão de ms, ou 11 dias. Por outro lado, com a busca binária, levará apenas 32 ms no pior dos casos:
Parece claro que os tempos de execução de uma busca simples e de uma busca binária não têm a mesma taxa de crescimento. Conforme o número de entradas na lista aumenta, a busca binária leva apenas um tempo minúsculo a mais para ser executada. Já o tempo de execução da busca simples aumenta exponencialmente à medida que a lista de entradas cresce.
É por isso que saber como aumenta o tempo de execução em relação ao tamanho da lista é tão importante. É exatamente por isso que a notação Big O é tão útil.
A notação Big O mostra o número de operações
Como mencionamos acima, a notação Big O não mostra o tempo que um algoritmo leva. Em vez disso, ele mostra o número de operações que o algoritmo realizará. Ele mostra a velocidade na qual um algoritmo cresce e permite que o comparemos com outros algoritmos.
Aqui temos alguns algoritmos comuns e seus tempos de execução em notação Big O:
| NOTAÇÃO BIG O | ALGORITMO DE EXEMPLO |
|---|---|
| O(log n) | Busca binária |
| O(n) | Busca simples |
| O(n * log n) | Ordenação Quicksort |
| O(n2) | Ordenação de seleção |
| O(n!) | Problema do caixeiro viajante |
Agora, você já sabe o suficiente para começar a explorar a notação Big O. Cabe a você começar a comparar seus algoritmos.