O que é Big O Notation?

Em poucas palavras, Big O é uma forma de classificar quanto a sua função ou algoritmo é escalável.

Isso nos ajuda a determinar qual será o comportamento do nosso algoritmo no PIOR dos casos ou quanto tempo ele levará para ser completado baseado nos seus valores de entrada.

Ou seja, qual será a performance do seu código se o número de valores de entrada aumentar? Constante? Linear? Exponencial? Veremos logo abaixo.

1°- Constantes

O que são constantes? Bem, constantes são funções que independente da quantidade de valores de entrada passados, a performance do tempo de resposta dela se manterá a mesma. Abaixo vemos um exemplo desse tipo de função:

Como podemos ver, independente da quantidade de valores que colocarmos no array, nossa função sempre imprimirá apenas os valores das duas primeiras posições, então o tempo de saída dessa função se manterá sempre o mesmo.

O tipo de notação dessa função é O(1). Abaixo um gráfico para facilitar a interpretação do comportamento dessa função:

2°- Linear

Os algoritmos lineares ou funções lineares, são caracterizados por realizar uma interação com cada valor passado na entrada. Assim a quantidade de operações realizadas será correspondente ao número de valores informados. Abaixo um exemplo deste comportamento:

Podemos ver que esta função imprimirá cada valor armazenado dentro do array. Assim, se a nossa entrada de dados aumenta, nosso tempo de execução também.

Algoritmos deste tipo possuem uma notação O(n), sendo “n” o número de valores passados na entrada. Abaixo um gráfico para facilitar a interpretação do comportamento dessa função:

3°- Exponencial

O novo tipo de complexidade de tempo que vamos falar são os algoritmos exponenciais. Nesse tipo de algoritmo além de interagirmos com cada elemento de entrada, nós iremos realizar uma sub interação.

Na função acima, podemos ver que agora em cada interação que fazemos com um elemento do array, nós iremos imprimir todas as combinações possíveis daquele elemento com demais valores, então todos os possíveis pares são feitos, por isso temos um loop dentro de outro loop.

Então, para cada elemento que acrescentamos no array, o número de interações e o tempo de execução aumentará de maneira exponencial. O que torna algoritmos dessa família ineficientes e com baixa performance caso estejamos lidando com um grande número de entrada de dados.

Este algoritmo possui uma notação O(n²). Abaixo um gráfico exemplificando seu comportamento:

4° — Logaritmos

A última notação de tempo de complexidade que iremos ver é a Logarítmica. Esta família é considerada muita performática por nos oferecer uma opção de interação muito eficiente em casos com um grande número de valores de entrada.

Um ótimo exemplo de uma função deste gênero é a busca binária:

Vamos pensar sobre o conceito da busca binária. Em todas as buscas, essa função sempre receberá dois valores como parâmetros, sendo o primeiro um array de elementos (que já deve estar ordenado, por estarmos lidando com uma busca binária) e o segundo o valor que queremos achar dentro desse array.

A busca binária possui um tempo de complexidade logarítmico, pois em cada operação nós cortamos os valores de entrada que não satisfazem as condições de busca pela metade. Isto é bom pois nós vamos apenas verificar uma fração de valores do nosso input para achar o valor que estamos procurando.

Dando um exemplo da vida real, digamos que temos um dicionário físico e estamos procurando pela palavra “House”. Você abrirá o meio do dicionário e estaremos na letra M.

Você sabe que palavras que começam com a letra M estão depois de palavras que começam com a letra H, então você não irá verificar de M em diante, ficando com uma fração menor de possíveis valores.

Então novamente, nós iremos para o meio dessa nova fração de valores e estaremos na sessão F.

Nessa nova sessão, nós sabemos que palavras que começam com a letra F estão antes de palavras que começam com a letra H. Então novamente nós iremos dividir nossos valores e gerar uma nova fração.

Agora estamos na sessão I e seguindo a lógica anterior, iremos excluir os valores que não atendem mais as condições de busca.

Finalmente, agora o meio da fração é a letra H, logo encontramos o valor que estávamos procurando.´

Com isso podemos afirmar que a busca binária nesse cenário foi eficiente, pois realizamos apenas 4 operações para achar o valor que estávamos procurando, dentro da nossa entrada composta por 26 elementos.

Assim o processo de busca se torna mais performático e não crescerá proporcionalmente com o número de valores na entrada de dados, mas sim irá crescer de maneira logarítmica.

Logo se tivermos uma entrada com 4000 elementos, precisaremos realizar apenas 12 operações para encontrar o valor que estamos procurando.

A Busca Binária é um exemplo de algoritmo que possui um tempo de complexidade logarítmico e sua notação é simbolizada por O(log n). Abaixo temos o gráfico exemplificando seu comportamento:

Conclusão

Esse artigo foi apenas uma introdução simplificada do que é Big O Notation. Mas espero que com isso você tenha entendido o que é e para que serve essa técnica de análise de algoritmos.

Você provavelmente terá dificuldades de aplicar esse conceito em algumas situações complexas e em que o tempo de entrega do projeto ou atividade é curto, então não se preocupe caso não consiga aplicar de primeira, pois no mundo da tecnologia tudo depende do cenário em que você está inserido.

O importante é que vocẽ tenha uma noção básica desse conhecimento para que sua mentalidade como desenvolvedor mude ao analisar e desenhar algoritmos e para que em cenários onde a performance é um fator crucial você tenha conhecimento de como trabalhar com seu código da maneira correta.

Espero que tenha gostado!