Análise de Complexidade – Tempo e Espaço

Introdução

Olá a todos! Espero que estejam bem e seguros. Nesta aula, vamos abordar um dos temas mais importantes de Estrutura de Dados e Algoritmos (DSA): Análise de Complexidade, focando principalmente em Complexidade de Tempo e Complexidade de Espaço.

Este é um dos tópicos mais relevantes para entrevistas técnicas, mas não se preocupe — apesar do nome, o conceito é mais simples do que parece.

Por que precisamos analisar algoritmos?

Existem várias maneiras de resolver um problema — assim como podemos viajar de um local para outro por diferentes meios (avião, carro, trem, etc.), cada algoritmo é uma rota diferente com seus prós e contras. A análise de algoritmos nos ajuda a escolher a melhor opção com base em fatores como:

• Tempo de execução
• Espaço (memória) necessário
• Corretude
• Escalabilidade
• Trade-offs entre tempo e espaço

O que é Análise de Complexidade?

Análise de Complexidade é uma parte da análise de algoritmos que se concentra em medir:

• Complexidade de Tempo: quanto tempo um algoritmo leva para ser executado em função do tamanho da entrada.
• Complexidade de Espaço: quanta memória ele consome durante a execução.

Essas métricas ajudam a escolher o algoritmo mais eficiente para determinado problema, principalmente em aplicações com grandes volumes de dados.

Complexidade de Tempo

Definição

A Complexidade de Tempo mede o crescimento do tempo de execução de um algoritmo à medida que o tamanho da entrada (n) aumenta.

⚠️ Importante: A complexidade de tempo não é o mesmo que o tempo real de execução (em milissegundos), que depende do hardware.

Exemplo: Busca Linear vs Busca Binária

• Busca Linear:
  • Percorre o array elemento por elemento.
  • Complexidade no pior caso: O(n)
  • Exemplo: Procurar por 30 em [10, 1, -1, 0, 20] exige até 5 comparações.
• Busca Binária:
  • Requer array ordenado.
  • Divide o array pela metade a cada iteração.
  • Complexidade: O(log n)
  • Muito mais eficiente para grandes volumes de dados.

Comparação Gráfica:

• O(n): cresce linearmente com o tamanho da entrada.
• O(log n): cresce de forma lenta, mesmo com aumento significativo do tamanho da entrada.

Medição de Complexidade

Notações Assimptóticas

1. Big-O (O): Pior caso (mais usada)
2. Ômega (Ω): Melhor caso
3. Teta (Θ): Caso médio

Regras Gerais

• Sempre considere o pior caso (Big-O)
• Ignore constantes (ex: O(n + 100) é O(n))
• Ignore termos menos dominantes (ex: O(n² + n) é O(n²))
• Foque em loops, chamadas recursivas e funções — operações executadas com frequência

Exemplos Práticos

Exemplo 1: Busca Linear

• Comparações no pior caso: n
• Complexidade: O(n)

Exemplo 2: Pares em um Array (Nested Loop)

• Cada par é gerado usando dois loops aninhados.
• Complexidade: O(n²)

Complexidade de Espaço

Definição

A Complexidade de Espaço é a quantidade de memória que o algoritmo consome durante sua execução, incluindo:

• Espaço fixo (entrada, variáveis)
• Espaço auxiliar (estruturas temporárias criadas durante a execução)

Exemplos

• Se um algoritmo usa apenas variáveis simples: O(1) (constante)
• Se cria uma cópia de um array de tamanho n: O(n)

Exemplo:

• Aqui, só usamos variáveis básicas.
• Complexidade de espaço: O(1)

Escalabilidade

Escalabilidade é a capacidade de um algoritmo ou aplicação de continuar performando bem à medida que o tamanho da entrada ou o número de usuários cresce.

Exemplo real: ao projetar um site, não se deve esperar que apenas 100 usuários o acessem. Ele deve funcionar mesmo que 1 milhão de usuários o acessem simultaneamente.

Resumo

Considerações Finais

• Entender a análise de complexidade é essencial para escrever códigos otimizados.
• É um dos tópicos mais perguntados em entrevistas.
• Nos próximos exemplos, vamos analisar diversos algoritmos e encontrar suas complexidades de forma prática.