Big O Notation
O que é Big O Notation, complexidade de tempo e de espaço? Como isso se aplica no dia a dia?
Olá pessoal , como estão?
Hoje quero falar um pouco sobre o famoso Big O, que sempre ouvimos falar, mas nunca temos certeza absoluta do que realmente é na prática, não é mesmo?
Big O é usado para classificar um algoritmo (seja em tempo de processamento ou de trabalho, também conhecido como espaço de memória). Então até agora, sabemos que o Big O classifica algoritmos em tempo e espaço.
Vamos falar um pouco sobre cada uma das 2, mas uma coisa que queria especificar antes é que ambas são baseadas em alguns aspectos, como: O que mede?, Unidade de medida e a Prioridade.
Big O - Tempo:
Basicamente, quando analisamos o tempo, literalmente analisamos o tempo. Ou seja, queremos ver, por exemplo, quanto tempo demora para percorrer uma lista não ordenada de 1 milhão de itens.
E qual unidade de medida usamos aqui? Você deve estar pensando em segundos ou minutos, mas não. Na verdade, utilizamos a quantidade de operações realizadas. Então, para percorrer a lista inteira, precisamos passar por todos os itens até o último, e a prioridade é reduzir o número de iterações até atingir o objetivo final.
Big O - Espaço:
Diferente do tempo, aqui nos preocupamos com outra coisa: a memória alocada. Isso é bem comum em embarcados. Quem nunca fez aquele projeto no Arduino na faculdade, né? Vai lembrar na certa!!!
Para enfatizar melhor a complexidade de tempo, aqui está um gráfico típico que mostra diferentes ordens de crescimento:
Vamos fazer uma analogia um pouco diferente para explicar os conceitos de experiência e nível. Basicamente, vamos passar por todas as constantes e sempre façam a análise baseado no pior e no melhor cenário do algoritimo.
O(1):
Quando nossa complexidade é O(1), estamos no melhor cenário possível em termos de complexidade de tempo, mas esse caso é raramente atingível no dia a dia.
Pensem que temos 1 banana e queremos 1 banana descascada. Basicamente, fazemos a operação apenas uma vez, ou seja, descascar essa única banana.
Em linguagem de programação, seria como acessar um índice de um array diretamente, por exemplo:
console.log(array[9]);O(N):
Nesse caso, O(N) significa que N é o número de vezes que precisamos realizar a operação.
Por exemplo, se temos 100 bananas e queremos 100 bananas descascadas, precisamos descascar O(N), onde N é o número de bananas que temos.
Esse cenário é muito comum quando iteramos por um array, percorrendo todos os elementos, seja de 0 a 5 ou de 0 a N.
O(N²):
Agora vamos reaproveitar a analogia. Quando temos O(N²), isso é o mesmo que O(N) x O(N).
Pense que temos 100 bananas, mas agora precisamos verificar as condições de cada uma em relação às outras, como verificar quais são boas e quais estão podres. No final, acabamos descascando 1000 bananas, porque o número de operações cresce de forma quadrática.
Considere uma matriz de [5][5]. Se fizermos dois loops para percorrê-la, teremos um total de 25 operações dentro dela.
O(log N):
Quando a complexidade é O(log N), o número de operações cresce lentamente à medida que o tamanho da entrada aumenta.
Pense que temos 1000 bananas organizadas em caixas e precisamos encontrar uma banana específica. Em vez de verificar banana por banana, usamos um método eficiente: abrimos a caixa no meio, verificamos se a banana está antes ou depois, e assim continuamos dividindo o problema ao meio até encontrar a banana.
Em termos de programação, um exemplo seria a busca binária
O(N log N):
Aqui combinamos os conceitos de O(N) e O(log N).
Imagine que temos 100 bananas misturadas e precisamos ordená-las rapidamente. Primeiro, dividimos as bananas em grupos menores (log N), e depois organizamos cada grupo (N). Esse é o comportamento típico de algoritmos de ordenação eficientes, como o Merge Sort ou o Quick Sort.
O(2ⁿ):
Quando a complexidade é O(2ⁿ), o número de operações dobra a cada nova unidade de entrada.
Imagine que temos 10 bananas, mas queremos descascar todas as combinações possíveis dessas bananas (ou seja, para 1 banana, 2 bananas, 3 bananas, e assim por diante). O número de combinações cresce exponencialmente, tornando o processo inviável para entradas grandes.
Um exemplo prático disso ocorre em algoritmos que resolvem problemas por força bruta, como o cálculo de subconjuntos em um conjunto.
O(N!):
Essa é a complexidade mais cara, onde as operações crescem de forma fatorial.
Imagine que temos 5 bananas e queremos descobrir todas as formas possíveis de organizá-las em uma fila. Primeiro, escolhemos 1 banana entre as 5, depois escolhemos outra entre as 4 restantes, e assim por diante, até que todas as combinações sejam testadas.
Um exemplo típico dessa complexidade é a resolução de problemas como o caixeiro-viajante por força bruta.
E aqui está porque fatorial é a complexidade mais cara é por isso:
Na prática:
Não é apenas em algoritmos ou em LeetCode que revisamos ou estudamos esses conceitos. Quero deixar um exemplo prático para vocês refletirem:
Pensem que temos uma tabela de likes e uma tabela de Posts. Para cada post, precisamos trazer todos os likes de outra tabela. Nesse caso, teríamos uma complexidade de O(N), já que precisamos percorrer todos os registros relacionados.
Agora, e se fizermos um contador para obter o número total de likes de um post sem ir na tabela de likes? Teríamos uma complexidade de O(1), que é muito mais barata para processar e mais eficiente para o usuário final.
Dessa forma, conseguimos aplicar o conceito de Big O no nosso dia a dia também!
Obrigado por lerem! Este é um breve artigo sobre Big O, cobrindo alguns casos de uso no dia a dia. Não é nada aprofundado, mas é uma boa base para iniciarem a jornada.