Complexidade de Algoritmos
Aula Relacionada recomendada:
Motivação
Pense no seguinte problema
Dado um array de \(n\) inteiros, sua tarefa é encontrar a soma máxima dos valores em um subarray contíguo e não vazio.
Nota
Tente resolver o problema antes de continuar a leitura.
Em competições de programação, a eficiência dos algoritmos é crucial. Embora seja geralmente mais simples conceber uma solução funcional, o verdadeiro desafio reside em otimizá-la. Uma solução ineficiente resultará em pouca ou nenhuma pontuação.
Análise de Complexidade
Queremos determinar o número de operações que um algoritmo executa em relação ao tamanho da entrada, \(n\). Para isso, utilizamos a Notação Big O, que descreve o pior caso da complexidade de tempo à medida que \(n\) se aproxima do infinito. Essa notação fornece um limite superior para o número de passos que um algoritmo pode requerer, em função do tamanho da entrada.
Quando expressamos a complexidade de uma função como \(O(f(n))\), geralmente omitimos fatores constantes e termos de ordem inferior de \(f(n)\). Veremos alguns exemplos práticos de como isso funciona a seguir.
Exemplos:
Operações constantes
O código a seguir é \(O(1)\), pois executa um número constante de operações.
Podemos assumir que operações de entrada (input) e saída (output) também são \(O(1)\).Loops
Uma causa comum para a lentidão de um algoritmo é a quantidade excessiva de loops que processam a entrada. Quanto mais loops aninhados seu algoritmo contiver, mais lento ele será. Se houver \(k\) loops aninhados, a complexidade de tempo será \(O(n^k)\).
O código a seguir tem complexidade \(O(n)\):
Como ignoramos fatores de ordem menor, o código abaixo também é \(O(n)\):
Para determinar a complexidade de loops aninhados, podemos multiplicar a complexidade de cada loop:Se um algoritmo possui múltiplos blocos de código, consideramos a complexidade como a pior complexidade entre todos os blocos.
Complexidade: \(O(n^2+m)\). Isso porque o primeiro bloco tem complexidade \(O(n^2)\) e o segundo tem complexidade \(O(m)\), e nenhuma delas é uma função de ordem inferior em relação à outra.
Recursão
A complexidade de uma função recursiva é determinada pelo número de vezes que a função é chamada multiplicado pela complexidade de cada chamada.
Considere a seguinte função:
f(1, n)
resulta em \(n\) chamadas da função, e cada uma delas tem complexidade \(O(1)\). Sendo assim, a complexidade total é \(O(n)\).
Agora, vejamos a próxima função:
fibonacci.cpp | |
---|---|
fib(n)
gera duas novas chamadas recursivas: fib(n - 1)
e fib(n - 2)
, exceto quando atinge os casos base, que são retornados diretamente sem gerar novas chamadas.
A árvore abaixo representa visualmente essa estrutura de chamadas para fib(5)

Observe que:
-
A árvore cresce para a esquerda e para a direita a cada chamada, como uma árvore binária.
-
Muitos valores são recalculados diversas vezes. Por exemplo,
fib(2)
é chamado 3 vezes,fib(1)
aparece 5 vezes.
Podemos estimar o número total de chamadas com a soma dos nós por nível:
Ou seja, a complexidade de tempo da versão recursiva de Fibonacci é exponencial, pois o número de chamadas cresce rapidamente com \(n\).
Complexidades Comuns e Restrições
- Fórmulas matemáticas que apenas calculam uma resposta: \(O(1)\)
- Busca binária: \(O(\log n)\)
- Operações em
Set
/Map
ouPriority Queue
: \(O(\log n)\) por operação - Fatoração prima ou verificação de número primo: \(O\sqrt{n}\)
- Leitura \(n \) itens de entrada: \(O(n)\)
- Iteração por um array ou lista de \(n \) elementos: \(O(n)\)
- Ordenação (Sorting): Geralmente implementado em \(O(n \cdot \log n)\) nas funções de ordenação da linguagem.
- Iterar por todos os subconjuntos de tamanho k de uma lista: \(O(n^k)\)
- Iterar por todos os subconjuntos: \(O(2^n)\)
- Iterar por todas as permutações: \(O(n!)\)
Aqui estão limites superiores conservadores para o valor de \(n\) para cada complexidade de tempo.
Você pode conseguir um desempenho melhor em alguns casos, mas esta tabela te ajudará a verificar rapidamente a viabilidade de um algoritmo.
\(n\) | Complexidades possíveis |
---|---|
\(n \leq 10\) | \(O(n!), O(n^7), O(n^6)\) |
\(n \leq 20\) | \(O(2^nn), O(n^5)\) |
\(n \leq 80\) | \(O(n^4)\) |
\(n \leq 400\) | \(O(n^3)\) |
\(n \leq 7500\) | \(O(n^2)\) |
\(n \leq 7 \cdot 10^4\) | \(O(n \sqrt n)\) |
\(n \leq 5 \cdot 10^5\) | \(O(n \log n)\) |
\(n \leq 5 \cdot 10^6\) | \(O(n)\) |
\(n \leq 10^{18}\) | \(O(\log^2 n), O(\log n), O(1)\) |
Uma estimativa conservadora para o número de operações que o servidor pode lidar por segundo é de \(10^8\), mas esse número pode chegar mais próximo de \(5 \cdot 10^8\) se os fatores constantes forem favoráveis.
Motivação: Maximum Subarray Sum
1ª Solução
Uma maneira direta de resolver o problema é iterar sobre todos os subarrays possíveis, calcular a soma de cada um e registrar a maior soma encontrada.
O código a seguir implementa essa abordagem:
A complexidade dessa solução é \(O(n^3)\). Como \(n\) pode ser da ordem de \(2 \cdot 10^5\), essa abordagem se torna inviável para a maioria dos casos.
2ª Solução
Para otimizar a complexidade, podemos usar o seguinte raciocínio: vamos nos concentrar em encontrar o subarray de maior soma que termina na posição \(k\). Existem duas possibilidades para esse subarray:
-
Ele contém apenas o elemento na posição \(k\).
-
Ele é formado pelo subarray de maior soma que termina na posição \(k−1\), seguido pelo elemento na posição \(k\).
Considerando que estamos buscando a soma máxima global, o subarray que termina na posição \(k−1\) também deve ter a maior soma possível para que a soma total seja máxima. Com essa ideia, podemos resolver o problema eficientemente, calculando a soma máxima do subarray que termina em cada posição, da esquerda para a direita.
O código a seguir implementa essa abordagem: