Você já ouviu falar em Big-O?

Em um mundo movido a dados, a eficiência do código pode ser a diferença entre uma solução elegante e um gargalo computacional. É aqui que entra a Notação Big O, uma ferramenta essencial para qualquer programador que busca escrever código limpo, rápido e escalável.

O Que é Big O?

Imagine um chef preparando um banquete. A Notação Big O seria como uma forma de descrever a rapidez com que o chef cozinha, dependendo do número de convidados. Ela não mede o tempo exato em minutos, mas sim como o tempo de cozimento aumenta à medida que mais pessoas se juntam à festa.

No contexto da programação, Big O descreve a eficiência de um algoritmo em relação ao tamanho da entrada (os "convidados"). Ele nos permite comparar diferentes algoritmos e entender como eles se comportarão com grandes conjuntos de dados.

Exemplos Comuns:

O(1) - Constante: O tempo de execução é independente do tamanho da entrada.

Em código: Acessar um elemento em um array usando seu índice:

array = [10, 5, 2, 7, 1]
print(array[3])  # Acessa o elemento no índice 3 (valor 7)

O(n) - Linear: O tempo de execução cresce proporcionalmente ao tamanho da entrada.

Em código: Encontrar o maior número em uma lista:

lista = [10, 5, 2, 7, 1]
maior = lista[0]
for numero in lista:
if numero > maior:
  maior = numero
print(maior)  # Saída: 10

O(log n) - Logarítmico: O tempo de execução cresce logaritmicamente com a entrada, tornando-o muito eficiente para grandes datasets.

Exemplo: Busca binária em uma lista ordenada.

def busca_binaria(lista, alvo):
inicio = 0
fim = len(lista) - 1
while inicio <= fim:
  meio = (inicio + fim) // 2
  if lista[meio] == alvo:
    return meio
  elif lista[meio] < alvo:
    inicio = meio + 1
  else:
    fim = meio - 1
return -1

lista = [2, 5, 7, 10, 11, 15]
print(busca_binaria(lista, 10))  # Saída: 3 (índice do 10)

O(n²) - Quadrático: O tempo de execução cresce exponencialmente com o tamanho da entrada, geralmente tornando-se ineficiente para grandes datasets.

Em código: Algoritmo Bubble Sort (ordenação por bolha) em sua pior performance:

def bubble_sort(lista):
n = len(lista)
for i in range(n):
  for j in range(0, n - i - 1):
    if lista[j] > lista[j + 1]:
      lista[j], lista[j + 1] = lista[j + 1], lista[j]
return lista

lista = [5, 1, 4, 2, 8]
print(bubble_sort(lista))  # Saída: [1, 2, 4, 5, 8]

Analisando e Otimizando Código com Big O:

Identificação: Analise seu código e identifique os loops, chamadas de funções recursivas e operações que mais impactam o tempo de execução.
Classificação: Atribua uma notação Big O a cada parte do seu código.
Gargalos: Concentre-se nas partes do código com a pior notação Big O, pois elas representam potenciais gargalos de performance.

def busca_lenta(lista, alvo):
"""
Busca um elemento em uma lista de forma ineficiente (O(n)).
"""
for i in range(len(lista)):
  if lista[i] == alvo:
    return i
return -1


def busca_binaria(lista, alvo):
"""
Busca um elemento em uma lista ordenada de forma eficiente (O(log n)).
"""
inicio = 0
fim = len(lista) - 1
while inicio <= fim:
  meio = (inicio + fim) // 2
  if lista[meio] == alvo:
    return meio
  elif lista[meio] < alvo:
    inicio = meio + 1
  else:
    fim = meio - 1
return -1