Complexidade de Algoritmos

1. Introdução: Por que analisar algoritmos?

No desenvolvimento de software de alto desempenho e competições: - Escrever código correto é apenas metade da batalha. - Garantir que execute dentro dos limites de tempo e memória é a outra metade.

Exemplo: Processamento de transações bancárias. - 10 transações em 1 seg \(\to\) OK. - \(1 \times 10^5\) transações em \(10^5\) seg (27 horas) \(\to\) Inviável.

Essa relação entre Tamanho da Entrada (\(N\)) vs Custo de Execução é a Análise de Complexidade.

O Modelo RAM

Para analisar algoritmos independentemente do hardware, usamos o modelo Random Access Machine (RAM): - Operações simples (+, -, *, if, call) levam 1 unidade de tempo. - Loops são compostos por várias operações simples. - Acesso à memória é constante \(O(1)\).

2. Notação Assintótica (Big O)

A notação Big O (\(O\)) descreve o limite superior do tempo de execução quando \(N \to \infty\). - Foco no Pior Caso. - Ignoramos constantes (ex: \(2N\) vira \(N\)). - Se \(N\) dobra, como o tempo cresce?

Se algoritmo é \(O(N^2)\), o tempo cresce quadraticamente.

Classes de Complexidade Comuns

Notação Nome Descrição Exemplo Típico
\(O(1)\) Constante O tempo não muda com \(N\). Acessar arr[i], operações aritméticas.
\(O(\log N)\) Logarítmica O problema é dividido em pedaços menores. Busca Binária, operações em TreeSet.
\(O(N)\) Linear Percorre a entrada uma vez. Loop simples, Busca Linear.
\(O(N \log N)\) Linearítmica Combinação de linear e logarítmico. Merge Sort, Heap Sort, Arrays.sort().
\(O(N^2)\) Quadrática Loop aninhado (todos com todos). Bubble Sort, Selection Sort.
\(O(N^3)\) Cúbica Três loops aninhados. Multiplicação de Matrizes ingênua.
\(O(2^N)\) Exponencial Tenta todas as subcombinações. Caixeiro Viajante (Força Bruta).
\(O(N!)\) Fatorial Tenta todas as permutações. Gerar anagramas.

3. Exemplos Práticos em Java

3.1. Complexidade Linear \(O(N)\)

O exemplo mais clássico é a Busca Linear. Precisamos verificar cada elemento até encontrar o alvo ou chegar ao fim.

public int buscaLinear(int[] vetor, int alvo) {
    // N é o tamanho do vetor
    for (int i = 0; i < vetor.length; i++) { // Executa N vezes no pior caso
        if (vetor[i] == alvo) {
            return i; // O(1)
        }
    }
    return -1;
}

Análise: No pior caso (elemento não existe ou está no final), o loop roda \(N\) vezes. Logo, \(O(N)\).

3.2. Complexidade Quadrática \(O(N^2)\)

Geralmente ocorre quando temos loops aninhados dependentes de \(N\). Um exemplo é verificar se há duplicatas comparando todos com todos.

public boolean temDuplicata(int[] vetor) {
    int n = vetor.length;
    for (int i = 0; i < n; i++) {           // Loop Externo: N vezes
        for (int j = i + 1; j < n; j++) {   // Loop Interno: ~N vezes
            if (vetor[i] == vetor[j]) {
                return true;
            }
        }
    }
    return false;
}

Análise: O loop interno roda \((N-1) + (N-2) + \dots + 1\), que é a soma aritmética \(\frac{N(N-1)}{2}\). Ignorando constantes e termos menores, temos \(\frac{N^2}{2} \approx O(N^2)\).

3.3. Complexidade Logarítmica \(O(\log N)\)

A Busca Binária é o exemplo fundamental. A cada passo, cortamos o espaço de busca pela metade. Isso só funciona se o vetor estiver ordenado.

public int buscaBinaria(int[] vetor, int alvo) {
    int inicio = 0;
    int fim = vetor.length - 1;
    
    while (inicio <= fim) {
        int meio = inicio + (fim - inicio) / 2; // Evita overflow de (inicio+fim)
        
        if (vetor[meio] == alvo) return meio;
        
        if (vetor[meio] < alvo) {
            inicio = meio + 1; // Descarta metade esquerda
        } else {
            fim = meio - 1;    // Descarta metade direita
        }
    }
    return -1;
}

Análise: Quantas vezes podemos dividir \(N\) por 2 até chegar a 1? A resposta é \(\log_2 N\). Para \(N = 1.000.000\), o loop executa apenas cerca de 20 iterações!

4. Analisando Recursão

Para algoritmos recursivos, nem sempre é óbvio olhar os loops. Usamos frequentemente o Teorema Mestre para dividir e conquistar.

Uma recorrência comum é: \(T(N) = aT(N/b) + f(N)\). - \(a\): número de chamadas recursivas. - \(N/b\): tamanho de cada subproblema. - \(f(N)\): custo para dividir/combinar.

Exemplo: Merge Sort O Merge Sort divide o vetor em 2 metades (\(a=2, b=2\)) e depois intercala as metades em tempo linear \(O(N)\). \[ T(N) = 2T(N/2) + O(N) \] Pelo Teorema Mestre, isso resulta em \(O(N \log N)\).

Códigos Recursivos “Ingênuos”: O cálculo de Fibonacci recursivo sem memorização:

public int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

Isso gera uma árvore de recursão onde cada nó gera 2 filhos. A altura da árvore é \(N\). Logo, \(O(2^N)\). Extremamente ineficiente para \(N > 40\).

5. Dicas para Maratonas e Juízes Online

Ao submeter um problema no Beecrowd, Codeforces ou LeetCode, você verá um “Time Limit” (geralmente 1 ou 2 segundos). Um computador moderno processa aproximadamente \(10^8\) operações simples por segundo.

Podemos usar essa regra de bolso para estimar se nossa solução vai passar (Time Limit Exceeded - TLE) ou não:

Tamanho da Entrada (\(N\)) Complexidade Esperada Algoritmos Sugeridos
\(N \leq 10\) \(O(N!)\) Permutação Completa
\(N \leq 20\) \(O(2^N)\) Backtracking, Bitmask DP
\(N \leq 500\) \(O(N^3)\) Floyd-Warshall, Multiplicação de Matrizes
\(N \leq 2.000\) \(O(N^2)\) Bubble Sort, DP 2D, Dijkstra (denso)
\(N \leq 10^5\) ou \(10^6\) \(O(N \log N)\) ou \(O(N)\) Sort padrão, Busca Binária, Hash Map, Árvores
\(N \leq 10^9\) \(O(\sqrt{N})\) Fatoração de Primos, Mo’s Algorithm
\(N \leq 10^{18}\) \(O(\log N)\) ou \(O(1)\) Exponenciação Rápida, Algoritmos Matemáticos

Exemplo de Análise Prévia

Problema: Dado um vetor de \(N=10^5\) números, encontre dois números que somam \(K\).

  1. Abordagem Força Bruta: Testar todos os pares.
    • Complexidade: \(O(N^2)\).
    • Operações: \((10^5)^2 = 10^{10}\).
    • Veredito: \(10^{10} > 10^8\). Muito lento. TLE.
  2. Abordagem Otimizada: Usar um HashSet ou ordenar.
    • Usando Sort + Two Pointers: \(O(N \log N)\).
    • Operações: \(10^5 \times 17 \approx 1.7 \times 10^6\).
    • Veredito: \(1.7 \times 10^6 < 10^8\). Passa com folga (Accepted).

6. Complexidade de Espaço

Não esqueça da memória! “Memory Limit Exceeded” (MLE) também é um erro comum. - \(O(1)\): Usa algumas variáveis auxiliares (int, float). - \(O(N)\): Usa um vetor auxiliar do tamanho da entrada. - \(O(N^2)\): Cria uma matriz \(N \times N\) (Cuidado! Para \(N=10.000\), uma matriz de inteiros gasta 400MB, estourando limites comuns de 256MB).

Na prática, sempre tente reduzir a complexidade de tempo primeiro, mas fique atento se você não está alocando memória demais (ex: recursão muito profunda estoura a Stack, tabelas de DP gigantes estouram a Heap).

Back to top