🔎 Desvendando Big O, o "Ozão"
Olá! 🐢
Me chamo Luiz Henrique, e neste post falarei brevemente sobre a Notação Big O, um fundamento básico e essencial, mas muito ignorado atualmente.
Por que devo aprender isso?
Se imagine usando uma rede social como Twitter, Instagram, Facebook ou semelhantes. Imagine seu feed demorando décadas para carregar, sua pesquisa por um conteúdo ficar dando loading infinitamente, ou você nem conseguisse abrir seu perfil pois suas centenas de posts nunca carregam. Sem o uso de algoritmos otimizados e sem desenvolvedores que saibam avaliar qual algoritmo usar e o por quê, seria exatamente isso que aconteceria.
O conhecimento em Big O permite a avaliação do desempenho de um algoritmo, permitindo maior escalabilidade e otimização. Principalmente em sistemas mais complexos, que lidam com grandes entradas de dados, ter um código que consiga lidar com muita informação sem perder performance é crucial, ainda mais nos dias de hoje, em que um carregamento demorado é rapidamente "punido".
Tá, mas o que é esse "Grande O", então?
A notação Big O (ou notação assintótica) é uma notação que provém da matemática, com uma definação formal e bem técnica, que não vale a pena entrar em detalhes aqui.
Na ciência da computação, é uma notação usada para definir a complexidade de um algoritmo, ou seja, quanto tempo ele leva pra executar conforme sua entrada de dados, referida como n, cresce. Ela também pode ser usada para definir a complexidade de espaço de mémoria que um algoritmo utiliza, porém, neste post, o foco será complexidade de tempo.
Simplificando: é uma forma de generalizar quanto tempo um algoritmo vai levar para ser executado, baseando-se na quantidade de dados que ele precisa processar.
A notação é escrita como O(1) (apenas um exemplo usando 1, que é uma das classificações da notação), e, em inglês, geralmente isso é lido como "Oh of 1" ou "Order of 1". Entre os parênteses, vai a generalização da complexidade, que pode ser 1 (como no exemplo), n, n², entre outras.
Ele analisa o pior caso, ou seja, o caso que levaria mais tempo naquela ocasião. Por exemplo, ao percorrer um array à procura de um valor, o pior caso é quando o valor está no último index, ou quando se percorre todo o array e não se encontra o valor. Nesses casos, o algoritmo percorreu todos os elementos do array, sendo assim, o pior caso, o caso mais custoso ou mais demorado.
Esse exemplo acima representa o algoritmo Linear Search, que percorre cada item de um array, sequencialmente. Ele possui tempo O(n) ("Oh of n" ou "Order of n"), ou seja, sua complexidade cresce de acordo com quanto a entrada de dados n cresce. Mais detalhes no próximo tópico.
Ok, mas como funciona?
A notação Big O possui algumas generalizações (como mostrado na imagem mais acima), como O(1), O(n), O(log n), etc. Cada algoritmo possui sua generalização, que segue algumas regras:
1. A notação Big O ignora constantes. Ou seja, não existe uma generalização O(2n), por exemplo. Nesse caso, seria utilizado apenas O(n).
2. A notação sempre usa a maior generalização presente no algoritmo. Se um algoritmo tiver duas partes, em que uma é O(n) e outra é O(n²), se diz que é um algoritmo O(n²), apenas.
3. É sempre considerado o pior caso, ou seja, o que necessita de mais passos para ser concluído.
Vamos a alguns exemplos:
Exemplo 1
const printFirstElement = (array) => {
if (array.length > 0) {
console.log(array[0]);
} else {
console.log("Array vazio.");
}
}
Este é um código simples, que, dado um array, checa se ele possui algum elemento. Se sim, esse elemento é mostrado; se não, é mostrado "Array vazio.".
É perceptível que, independentemente do tamanho do array, o algoritmo sempre irá se comportar de maneira igual, sem adicionar passos extras em sua execução. Logo, conclui-se que é um algoritmo de complexidade O(1), ou de tempo constante, pois sua complexidade não muda, não importando se o array possui 10, 100 ou 1.000.000 elementos.
Exemplo 2
const linearSearch = (array, target) => {
for (let i = 0; i < array.length; i++) {
if (array[i] === target) {
return i;
}
}
return -1;
};
Este é o algoritmo Linear Search, citado no tópico anterior. Como visto, ele possui complexidade O(n) em seu pior caso, que seria percorrer todo o array, fazendo com que haja uma iteração para cada elemento no array, ou seja, n iterações.
Por isso, essa generalização também é conhecida como linear, pois a complexidade cresce linearmente ao tamanho do input (entrada de dados). Se o array possuir 5 elementos, serão 5 iterações; se possuir 10, serão 10 iterações; se possuir 1.000, 1.000 iterações; e assim sucessivamente (lembre-se, considerando o pior caso!).
Exemplo 3
const processArray = (array) => {
for (let i = 0; i < array.length; i++) {
console.log(array[i]); // O(1)
} // O(n)
for (let j = array.length - 1; j >= 0; j++) {
console.log(array[j]); // O(1)
} // O(n)
};
Esse é um método que exibe os elementos do array de forma crescente e decrescente, em dois loops separados.
Esse algoritmo poderia ser classificado como O(2n), afinal, possui dois loops com complexidade O(n)! Mas não é assim que funciona.
Lembre-se que a notação ignora constantes, ou seja, não existe O(2n), O(n + 5), entre outras. Esse algoritmo, por mais estranho que pareça, é considerado O(n), assim como o Linear Search.
Há também o fato de que há duas linhas de código que são O(1), mas elas também são "ignoradas", afinal, lembre-se também que deve se considerar a maior complexidade, que nesse caso, é O(n).
Há várias outras complexidades, porém, caso todas fossem exemplificadas aqui, o post se tornaria um TCC. Entretanto, com esses exemplos, entender as outras complexidades vai ser bem mais fácil.
Há um gráfico dessas complexidades, classificadas de acordo com sua qualidade e representando sua complexidade de acordo com a quantidade de operações necessárias e elementos. Aproveite!
Não leve ao pé da letra (ou pé do O)
A notação Big O é de grande importância para a análise de algoritmos, porém, como se trata de uma generalização bem regrada, possui algumas "falhas":
- Como Big O ignora constantes, pode ser que você se depare com algoritmos com tempos de execução bem diferentes, mas com a mesma complexidade segundo a notação ─ por exemplo, ao utilizar Big O, um algoritmo x O(n) e um algoritmo y O(5n) serão ambos considerados O(n), mas, na prática, o algoritmo x é bem mais rápido.
- O uso do pior caso pode gerar algumas confusões. Há algoritmos que são melhores que outros no pior caso, porém, são piores nos casos "médios" (average case, que é classificado com a notação Big Theta, do símbolo Θ) e melhores (best case, classificado com a notação Big Omega, do símbolo Ω), sendo assim, na prática, mais lentos (afinal, o average case é o que deve ocorrer com maior frequência)!
- A análise apenas do tempo de execução é um problema, pois, em alguns casos, outras coisas devem ser avaliadas também, como complexidade de espaço, uso de memória, entre outras.
Sendo assim, use sempre o "Ozão" a seu favor, mas saiba avaliar os algoritmos indo além dessa notação e complementando a análise com outros recursos!
Conclusão
Obrigado por ler até aqui! Espero que tenha gostado e aprendido com o post. Sinta-se livre para deixar seu feedback e opinião nos comentários. Deixarei aqui alguns links que me ajudaram na construção do post e que devem te ajudar nos estudos de Big O também!
Big O Cheat Sheet
Vídeo - Big O Notation: O Pesadelo do Programador Iniciante (Lucas Montano)
Vídeo - Big-O Notation in 100 Seconds (Fireship)
Vídeo - Big O Notation in 5 (Michael Sambol)