Quando analisamos algoritmos, um dos conceitos mais importantes é a complexidade de tempo e espaço. Ela nos permite medir o desempenho de um algoritmo, ajudando a prever como ele se comporta à medida que a quantidade de dados de entrada cresce. A Notação Big O é a principal ferramenta utilizada para descrever essa complexidade, permitindo comparar a eficiência de diferentes algoritmos.

Complexidade de Tempo

A complexidade de tempo representa o crescimento do tempo de execução de um algoritmo em relação ao tamanho da entrada. Para essa análise, não consideramos o tempo absoluto em segundos, mas sim uma estimativa do crescimento do número de operações conforme aumentamos a entrada.

Por exemplo:

Se um algoritmo tem complexidade O(n), ele realiza um número de operações proporcional ao tamanho da entrada.
Se um algoritmo tem complexidade O(n²), ele realiza um número de operações proporcional ao quadrado do tamanho da entrada.

Complexidade de Espaço

Enquanto a complexidade de tempo analisa a performance em relação ao tempo, a complexidade de espaço avalia o consumo de memória de um algoritmo. Ela mede a quantidade de espaço adicional necessária para executar o algoritmo, além dos dados de entrada. Isso inclui o uso de variáveis auxiliares, alocação de estruturas de dados e chamadas recursivas.

Por que complexidade de tempo é importante?

Imagine que você precisa resolver um problema e tem duas opções de algoritmos. Ambos funcionam corretamente, mas um deles leva 10 segundos para processar 10.000 dados, enquanto o outro leva apenas 1 segundo. Qual você escolheria? Obviamente, o mais rápido! A complexidade de tempo nos ajuda a prever essas diferenças de desempenho sem precisar testar os algoritmos com entradas enormes.

Um ponto importante é que ignoramos constantes e fatores menores. Um algoritmo com complexidade O(2n) e outro com O(10n) pertencem à mesma "família" de complexidade, O(n), porque ambos crescem linearmente com o tamanho da entrada.

Isso significa que, ao analisar um algoritmo, focamos no comportamento assintótico — ou seja, como ele cresce quando N se torna muito grande. Um algoritmo eficiente pode fazer a diferença entre um processamento rápido e um que leva horas ou até dias para concluir.

Complexidade O(1) - Tempo Constante

Um algoritmo com complexidade O(1) tem um tempo de execução constante, independentemente do tamanho da entrada.

Exemplos de operações em O(1):

1. Acesso e atualização em um array

O acesso direto a um índice específico em um array ocorre em tempo constante.

arr = [1, 2, 3, 4, 5]
valor = arr[2]  # Acesso O(1)
arr[2] = 99  # Atualização O(1)

2. Inserção e remoção em uma pilha (stack)

Adicionar ou remover um elemento do topo da pilha tem tempo constante.

stack = []
stack.append(5)  # Push O(1)
stack.append(10)  # Push O(1)
stack.pop()  # Pop O(1)

3. Busca em um dicionário (HashMap)

A busca por uma chave em um dicionário ocorre em tempo O(1) na maioria dos casos.

hashmap = {"a": 1, "b": 2, "c": 3}
valor = hashmap["b"]  # Lookup O(1)
hashmap["d"] = 4  # Inserção O(1)

4. Aplicação de uma fórmula matemática

Cálculos matemáticos diretos, como encontrar a média de dois números, ocorrem em tempo constante.

def media(a, b):
    return (a + b) / 2  # O(1)

resultado = media(10, 20)

Complexidade O(log n) - Tempo Logarítmico

Um algoritmo com complexidade O(log⁡ n) tem um tempo de execução que cresce logaritmicamente com o tamanho da entrada.

O exemplo mais clássico de um algoritmo com complexidade de tempo O(log n) é a Busca Binária. A ideia central por trás dessa complexidade é a capacidade de "dividir pela metade" o espaço de busca a cada iteração, reduzindo o número de operações necessárias para encontrar a solução. O tempo de execução cresce de forma logarítmica em relação ao tamanho da entrada. Isso significa que, mesmo que o tamanho da entrada dobre, o número de operações aumenta apenas em uma quantidade constante. Essa eficiência é alcançada ao dividir repetidamente o problema em partes menores, descartando uma fração significativa dos dados a cada passo.

i = 1_000_000
resultado = []
while i > 0:
    resultado.append(i)
    i = i // 2
print(resultado)
# Saída: [1000000, 500000, 250000, 125000, 62500, 31250, 15625, 7812, 
#         3906, 1953, 976, 488, 244, 122, 61, 30, 15, 7, 3, 1]
print(len(resultado))
# Saída: 20

O que acontece aqui?

A cada iteração, o valor de i é dividido pela metade (i = i // 2).
Iniciando com i = 1.000.000, o loop termina após 20 iterações, quando i se torna 0.
Se duplicarmos o valor inicial para i = 2.000.000, o número de iterações aumenta apenas para 21.

Esse comportamento é típico de algoritmos O(log n): mesmo que o tamanho da entrada dobre, o número de operações aumenta pouco.

Complexidade O(n) - Tempo Linear

Um algoritmo com complexidade O(n) tem um tempo de execução que cresce linearmente com o tamanho da entrada.

Exemplos de operações em O(n):

1. Busca Linear em uma Lista

def busca_linear(lista, alvo):
    for elemento in lista:
        if elemento == alvo:
            return True
    return False

lista = [1, 2, 3, 4, 5]
print(busca_linear(lista, 3))  # Saída: True
print(busca_linear(lista, 6))  # Saída: False

2. Contagem de Elementos em uma Lista

def contar_elemento(lista, alvo):
    contagem = 0
    for elemento in lista:
        if elemento == alvo:
            contagem += 1
    return contagem

lista = [1, 2, 3, 4, 2, 2, 5]
#.          ^        ^  ^
alvo = 2
print(contar_elemento(lista, alvo))  # Saída: 3

Complexidade O(n log n) - Tempo log-linear

Um algoritmo com complexidade O(n log n) é comum em algoritmos de ordenação eficientes, como o Merge Sort.

Assim como a complexidade logarítmica, a complexidade O(n log n) tem um exemplo clássico que é o Merge Sort, um algoritmo de ordenação. A ideia central por trás dessa complexidade é combinar a eficiência de operações logarítmicas com a necessidade de processar todos os elementos da entrada. Enquanto algoritmos O(log n) focam em dividir o problema em partes menores, algoritmos O(n log n) realizam essa divisão e processam cada elemento da entrada em cada etapa.

Complexidade O(n²) - Tempo Quadrático

Um algoritmo com complexidade O(n²) tem um tempo de execução que cresce quadraticamente com o tamanho da entrada.

Exemplos de operações em O(n²):

1. Soma de Todos os Elementos em uma Matriz

def soma_matriz(matriz):
    soma = 0
    n = len(matriz)
    for i in range(n):
        for j in range(n):
            soma += matriz[i][j]  # Adiciona cada elemento à soma
    return soma

# Exemplo de uso
matriz = [[1, 2], [3, 4]]
print(soma_matriz(matriz))  # Saída: 10

2. Gerar Todos os Pares Possíveis em uma Lista

def gerar_pares(lista):
    pares = []
    for i in lista:
        for j in lista:
            pares.append((i, j))  # Adiciona o par (i, j) à lista de pares
    return pares

# Exemplo de uso
lista = [1, 2, 3]
print(gerar_pares(lista))
# Saída: [(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]

Por que esses algoritmos são O(n²)?

Em todos os exemplos acima, o número de operações é proporcional ao quadrado do tamanho da entrada (n²). Isso significa:

Se n=10, o algoritmo realiza 100 operações.
Se n=10, o algoritmo realiza aproximadamente 10.000 operações.

Complexidade O(2^n) - Tempo exponencial

Algoritmos com complexidade O(2^n) são aqueles em que o tempo de execução dobra a cada aumento no tamanho da entrada. Essa complexidade é típica de problemas que envolvem combinações ou subconjuntos, onde o número de possibilidades cresce exponencialmente. Esses algoritmos são considerados ineficientes para entradas grandes, pois o tempo de execução se torna rapidamente inviável.

Exemplos de operações em O(2^n):

1. Gerar Todas as Combinações de um Conjunto

def gerar_combinacoes(conjunto):
    if not conjunto:
        return [[]]  # Retorna uma lista contendo o conjunto vazio
    primeiro = conjunto[0]
    resto = conjunto[1:]
    combinacoes_resto = gerar_combinacoes(resto)
    combinacoes_com_primeiro = [[primeiro] + comb for comb in combinacoes_resto]
    return combinacoes_resto + combinacoes_com_primeiro

# Exemplo de uso
conjunto = [1, 2, 3]
print(gerar_combinacoes(conjunto))
# Saída: [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

Quando usar algoritmos O(2^n)?

Apesar de sua ineficiência, algoritmos O(2^n) são úteis em cenários específicos:

Problemas com entradas pequenas: Se o tamanho da entrada for limitado (por exemplo, n≤20n≤20), algoritmos exponenciais podem ser aceitáveis.
Problemas de combinação ou subconjuntos: Quando é necessário explorar todas as possibilidades, como em problemas de otimização ou backtracking.

Complexidade O(n!) - Tempo Fatorial

Algoritmos com complexidade O(n!) são aqueles em que o tempo de execução cresce fatorialmente com o tamanho da entrada. Isso significa que, para uma entrada de tamanho n, o número de operações é proporcional a n! (fatorial de n). A complexidade fatorial é uma das piores em termos de eficiência, pois o tempo de execução explode rapidamente, mesmo para entradas pequenas.

O fatorial de um número nn (denotado por n!) é o produto de todos os números inteiros positivos de 1 até n. Por exemplo:

3! = 3×2×1 = 6
5! = 5×4×3×2×1 = 120
10! = 10×9×8×7×6×5×4×3×2×1 = 3.628.800

Como você pode ver, o valor de n! cresce extremamente rápido, tornando algoritmos O(n!) inviáveis para entradas grandes.

Alguns problemas clássicos que envolvem soluções com complexidade O(N!) incluem: o Problema do Caixeiro Viajante (Traveling Salesman Problem), a Geração de Permutações (Permutations), o Problema das N-Rainhas (N-Queens), a Geração de Subconjuntos (Subsets), e o Problema de Coloração de Grafos (Graph Color ing). Esses problemas exigem a exploração de todas as possibilidades, resultando em complexidade fatorial.

Notação Big O

Table of contents