Complexidade de Algoritmos: medir a eficiência do código

Um algoritmo que funciona perfeitamente com 100 elementos pode se tornar inutilizável com 10 milhões. A diferença entre um algoritmo ruim e um bom não é de segundos — pode ser de dias. Entender complexidade é o que separa código que escala de código que trava.

Exemplo real: buscar um nome em uma lista telefônica de 1 milhão de entradas. Se você verificar um a um desde o início, pode precisar de 1 milhão de comparações. Com a busca binária (que funciona em listas ordenadas), você encontra qualquer nome em no máximo 20 comparações. A diferença é de 1.000.000 para 20.

Complexidade de algoritmos é a área da ciência da computação que estuda como o tempo de execução e o uso de memória crescem conforme o tamanho da entrada aumenta. A ferramenta principal é a notação Big-O.

A notação Big-O descreve como o custo de um algoritmo cresce em relação ao tamanho da entrada n, no pior caso. Ela ignora constantes e termos menores para focar no comportamento dominante com entradas grandes.

O(1) — tempo constante: o algoritmo leva o mesmo tempo independentemente do tamanho da entrada. Acessar um elemento de um array pelo índice é O(1) — não importa se o array tem 10 ou 10 milhões de elementos, o acesso é igualmente rápido.

O(n) — tempo linear: o tempo cresce proporcionalmente ao tamanho da entrada. Percorrer todos os elementos de uma lista para encontrar o maior valor é O(n): com o dobro de elementos, leva o dobro do tempo.

O(n²) — tempo quadrático: o tempo cresce com o quadrado do tamanho da entrada. Algoritmos com dois loops aninhados que percorrem toda a coleção costumam ser O(n²). Com 1000 elementos são necessárias até 1.000.000 operações.

O(log n) — tempo logarítmico: o tempo cresce muito lentamente. A cada passo, o problema é dividido ao meio. A busca binária em uma lista ordenada de 1 bilhão de elementos precisa de no máximo 30 comparações.

A busca linear percorre os elementos um a um desde o início até encontrar o alvo ou chegar ao final. É simples, funciona em qualquer lista (ordenada ou não), mas é O(n) — no pior caso, verifica todos os elementos.

A busca binária funciona apenas em listas ordenadas. Ela começa pelo elemento do meio: se o alvo é menor, descarta a metade superior e repete na metade inferior; se é maior, descarta a metade inferior. A cada passo, o espaço de busca é dividido ao meio, resultando em complexidade O(log n).

Para uma lista de 1.000.000 de elementos, a busca linear pode precisar de até 1.000.000 comparações. A busca binária precisa de no máximo 20. O custo de manter a lista ordenada é amortizado quando há muitas buscas — ordenar uma vez e buscar rapidamente muitas vezes vale a pena.

Ordenar uma coleção é uma das tarefas mais comuns em programação. A escolha do algoritmo de ordenação impacta diretamente a performance para coleções grandes.

O Bubble Sort é o mais simples de entender: percorre a lista repetidamente, comparando pares adjacentes e trocando os que estão fora de ordem. O maior elemento vai borbulhando para o final a cada passagem. É intuitivo, mas tem complexidade O(n²) — extremamente lento para listas grandes. Não é usado em produção.

O Merge Sort (ordenação por mesclagem) usa a estratégia de divisão e conquista: divide a lista ao meio recursivamente até ter listas de um elemento (que já estão ordenadas), depois mescla os pares de listas menores em ordem crescente. A mesclagem de duas listas ordenadas é O(n), e o processo se repete O(log n) vezes, resultando em O(n log n) no total. Essa é a complexidade ótima para algoritmos de ordenação baseados em comparação.

As linguagens modernas usam variantes do Merge Sort ou Quick Sort internamente. Python usa Timsort (híbrido de Merge Sort e Insertion Sort). Java e JavaScript usam variantes similares. Você raramente precisará implementar um algoritmo de ordenação do zero — mas entender a complexidade ajuda a tomar decisões informadas.

Além do tempo, algoritmos também consomem memória. A complexidade de espaço mede como o uso de memória cresce com o tamanho da entrada. Um algoritmo pode ser rápido (O(n log n)) mas consumir O(n) de memória extra — o que pode ser um problema em dispositivos com memória limitada.

Trade-off é a troca consciente entre recursos. Às vezes, usar mais memória permite reduzir o tempo de execução. Um exemplo clássico é a memoização: armazenar resultados já calculados para não recalcular. O cálculo recursivo de Fibonacci sem memoização é O(2^n); com memoização, cai para O(n) no tempo ao custo de O(n) em memória.

Na prática, o primeiro passo é fazer o algoritmo funcionar corretamente. Depois, se houver problema de performance, meça antes de otimizar — ferramentas de profiling mostram exatamente onde o tempo está sendo gasto. Otimizar o código certo é muito mais eficaz do que otimizar tudo às cegas.