Complexidade de Algoritmos

Data de Publicação

09/03/2026

Data de Modificação

09/03/2026

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 (dinâmica):

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 chamadas filhas: - Nível 0: 1 chamada - Nível 1: 2 chamadas - Nível 2: 4 chamadas … Nível \(N\): \(2^N\) chamadas.

O total de operações soma a progressão geométrica \(1 + 2 + 4 + \dots + 2^{N-1} = 2^N - 1\). A complexidade, portanto, é \(O(2^N)\). Isso se torna 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

Por que \(\leq 500\) aceita \(O(N^3)\)?
Se a entrada \(N = 500\), então \(500^3 = 125.000.000 \approx 1.25 \times 10^8\). Esse valor fica exatamente ali próximo ao limiar tolerado de \(10^8\) operações em 1 segundo. Ou seja, qualquer algoritmo cúbico de constante alta falharia para \(N \geq 500\) tomando TLE.

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).

Limites práticos para Ordenações Comuns

E quando os algoritmos de ordenação estouram o tempo limite de \(10^8\) operações?

  • Bubble Sort (\(O(N^2)\)):
    • Para \(N = 10.000\) (\(10^4\)): \((10^4)^2 = 10^8\) operações. (Passa raspando).
    • Para \(N = 100.000\) (\(10^5\)): \((10^5)^2 = 10^{10}\) operações. (TLE - Demoraria cerca de 100 segundos).
  • Merge/Quick Sort (\(O(N \log_2 N)\)):
    • Para \(N = 100.000\) (\(10^5\)): \(10^5 \times 17 \approx 1.7 \times 10^6\) operações. (Passa com folga - Gasta \(\approx 0.01s\)).
    • Para \(N = 1.000.000\) (\(10^6\)): \(10^6 \times 20 \approx 2 \times 10^7\) operações. (Passa com folga - Gasta \(\approx 0.2s\)).

6. Complexidade de Espaço

Não esqueça da memória! O veredito “Memory Limit Exceeded” (MLE) também é um erro comum em problemas competitivos. - \(O(1)\): Usa algumas variáveis auxiliares (int, double). - \(O(N)\): Usa um vetor auxiliar do tamanho exato da entrada. - \(O(N^2)\): Cria uma matriz \(N \times N\).

Qual o limite prático para alocação no Java? O tipo int ocupa 4 bytes em Java. Portanto: - 1 MB é capaz de armazenar cerca de \(\approx 250.000\) inteiros. - 512 MB serviria idealmente para alocar até \(128\) milhões de inteiros (\(\approx 1.28 \times 10^8\)).

Atenção: A JVM usa muito overhead arquitetural, objetos como Integer gastam bem mais memória e o Garbage Collector precisa de margem. Na prática, alocar int[100_000_000] pode acionar rapidamente o limite dependendo do juiz da competição. Uma matriz \(10.000 \times 10.000\) suga rapidamente 400 MB, estourando o teto típico de 256MB de muitos juízes.

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 gigantes de DP estouram a Heap).

7. Gargalos de Entrada e Saída (I/O)

Mesmo que sua complexidade de tempo seja excelente (\(O(N)\)), seu código pode tomar TLE simplesmente pela lentidão na leitura/escrita de dados massivos na tela.

O Problema no Java: - A classe Scanner é muito lenta porque faz parsing robusto usando Expressões Regulares por baixo dos panos. - System.out.println descarrega o buffer na tela a cada chamada, o que é custoso e trava a thread da JVM.

Quando me preocupar (Regra de Ouro dos \(10^5\)): - Se o problema exige ler/imprimir \(10^5\) ou mais números/linhas. - Substitua Scanner por BufferedReader e StringTokenizer (combinação também chamada de “Fast I/O”). - Substitua chamadas a println() em loops grandes por concatenações de StringBuilder ou utilize o fluxo otimizado de um PrintWriter.

8. Análise Amortizada

Às vezes, uma operação pode ser lenta no pior caso, mas, quando avaliada ao longo de MUITAS execuções, o custo médio (amortizado) se dilui e fica excelente.

O Clássico ArrayList.add()

Quando você insere num ArrayList em Java, a complexidade geralmente é \(O(1)\).

Porém, quando o array interno enche, o Java precisa: 1. Criar um novo array interno maior (geralmente +50% em Java). 2. Copiar todos os \(N\) elementos para o novo vetor (custo pesado e imediato de \(O(N)\)).

Logo, no pior caso o add() é \(O(N)\). No entanto, como o aumento de tamanho acontece de fato exponencialmente espaçado, o custo “caro” das cópias se dilui ao longo das muitas inserções \(O(1)\) acumuladas que antecederam aquilo.

Conclusão: Dizemos formalmente que a inserção sistemática no ArrayList tem um custo de desempenho excelente de \(O(1)\) amortizado.

De volta ao topo