Complexidade de Algoritmos e Estruturas de Dados

Conceitos Fundamentais

A complexidade é uma medida que nos permite analisar e comparar a eficiência de algoritmos e estruturas de dados. ¹ ² ³ ⁴

Ela responde à pergunta fundamental: “Como o desempenho muda conforme o tamanho da entrada aumenta?”

Tipos de Complexidade

Complexidade de Tempo:
Mede quanto tempo um algoritmo leva para executar em função do tamanho da entrada (n).

Complexidade de Espaço:
Mede quanta memória adicional o algoritmo precisa além da entrada original.

Notação Big O

A notação Big O (O) descreve o comportamento assintótico - como o algoritmo se comporta para valores grandes de n.

Principais complexidades (da melhor para a pior):

O(1) - Constante: Tempo não depende do tamanho da entrada
- Exemplo: Acessar um elemento de array por índice
O(log n) - Logarítmica: Muito eficiente, divide o problema pela metade
- Exemplo: Busca binária, árvores balanceadas
O(n) - Linear: Tempo cresce proporcionalmente à entrada
- Exemplo: Percorrer um array, busca linear
O(n log n) - Log-linear: Comum em algoritmos eficientes de ordenação
- Exemplo: Merge sort, quick sort (caso médio)
O(n²) - Quadrática: Tempo cresce com o quadrado da entrada
- Exemplo: Bubble sort, insertion sort, selection sort
O(2ⁿ) - Exponencial: Muito ineficiente, cresce exponencialmente
- Exemplo: Alguns algoritmos de força bruta

Por que é importante?

Escalabilidade: Permite prever como o algoritmo se comportará com dados maiores.
Comparação: Facilita escolher entre diferentes soluções para o mesmo problema.
Otimização: Identifica gargalos e oportunidades de melhoria.
Tomada de decisão: Ajuda a decidir qual estrutura de dados ou algoritmo usar em cada situação.

Exemplo Prático

Para ordenar 1000 elementos:

Bubble Sort O(n²): ~1.000.000 operações
Merge Sort O(n log n): ~10.000 operações

Para ordenar 10.000 elementos:

Bubble Sort: ~100.000.000 operações (100x mais!)
Merge Sort: ~130.000 operações (13x mais)

Análise de Casos

Melhor caso: Cenário mais favorável
Caso médio: Comportamento típico esperado
Pior caso: Cenário mais desfavorável

A análise do pior caso é geralmente mais importante para garantir que o sistema funcione adequadamente mesmo em condições adversas.

A complexidade é, portanto, uma ferramenta essencial para escrever código eficiente e tomar decisões informadas sobre qual solução usar em cada contexto.

Existem vários algoritmos conhecidos para lidar com diferentes estruturas de dados. Aqui estão alguns deles:

Complexidade do merge sort e quick sort
Exemplo prático de crescimento quadrático
Estruturas de dados para procedimentos recursivos
Usos de árvores
Complexidade de inserção em árvores balanceadas

1. Complexidade do Merge Sort

Uma das principais vantagens do merge sort é sua estabilidade - ele mantém a ordem relativa de elementos iguais, além de ter desempenho previsível independentemente da distribuição inicial dos dados.

A complexidade do algoritmo merge sort é:

Complexidade de tempo:

Melhor caso: O(n log n)
Caso médio: O(n log n)
Pior caso: O(n log n)

Complexidade de espaço:

O merge sort tem uma complexidade de tempo consistente de O(n log n) em todos os casos porque:

Divisão: O algoritmo sempre divide o array pela metade recursivamente, criando uma árvore de recursão com altura log n
Conquista: Em cada nível da árvore, são feitas operações de merge que percorrem todos os n elementos
Resultado: log n níveis × n operações por nível = O(n log n)

A complexidade de espaço O(n) vem do fato de que o merge sort precisa de arrays auxiliares para fazer a fusão dos subarrays ordenados. Esta é uma desvantagem em relação a algoritmos como o heap sort, que ordenam “in-place” com O(1) de espaço adicional.

2. Complexidade do Quick Sort

A complexidade do algoritmo quick sort é:

Complexidade de tempo:

Melhor caso: O(n log n)
Caso médio: O(n log n)
Pior caso: O(n²)

Complexidade de espaço:

Melhor/Caso médio: O(log n) - devido à pilha de recursão
Pior caso: O(n) - quando a recursão é muito profunda

Detalhamento dos casos:

Melhor caso/Caso médio (O(n log n)):

Ocorre quando o pivô divide o array aproximadamente pela metade
Altura da árvore de recursão: log n
Operações por nível: n (particionamento)
Total: log n × n = O(n log n)

Pior caso (O(n²)):

Acontece quando o pivô é sempre o menor ou maior elemento
- Por exemplo: array já ordenado com pivô sendo sempre o primeiro elemento
Altura da árvore de recursão: n
Total: n × n = O(n²)

Estratégias para evitar o pior caso:

Pivô aleatório: escolher o pivô randomicamente
Mediana de três: usar a mediana entre primeiro, meio e último elemento
Quick sort híbrido: alternar para insertion sort em arrays pequenos

Vantagens do quick sort:

Ordenação “in-place” (baixo uso de memória)
Muito eficiente na prática
Cache-friendly devido à localidade de referência

Na prática, o quick sort é frequentemente mais rápido que o merge sort, apesar do pior caso quadrático.

3. Crescimento Quadrático

Pergunta: Para um algorítmo de crescimento quadrático, uma entrada de 1000 tem tempo de 20 ms. Qual o tempo para 10000?

Para resolver isso, é necessário usar a relação de crescimento quadrático.

Em um algoritmo O(n²), o tempo é proporcional ao quadrado do tamanho da entrada:

Relação: T(n) = k × n²

onde k é uma constante.

Dados:

n₁ = 1000, T₁ = 20 ms
n₂ = 10000, T₂ = ?

Cálculo:

Primeiro, encontro a constante k: T₁ = k × n₁² 20 = k × (1000)² 20 = k × 1.000.000 k = 20/1.000.000 = 0,00002

Agora calculo T₂: T₂ = k × n₂² T₂ = 0,00002 × (10000)² T₂ = 0,00002 × 100.000.000 T₂ = 2000 ms

Método mais direto: Como 10000 = 10 × 1000, e o crescimento é quadrático: T₂ = T₁ × (10)² = 20 × 100 = 2000 ms

Resultado: 2000 ms (aproximadamente 33 minutos e 20 ms)

Isso demonstra como algoritmos quadráticos se tornam impraticáveis rapidamente com o aumento do tamanho da entrada!

4. Estrutura de Dados para procedimento recursivo

Pergunta: Qual estrutura de dados para um procedimento recursivo?

stack
array
lista
queue

A resposta é 1. stack (pilha).

Por que stack é a estrutura correta:

A recursão funciona com o princípio LIFO (Last In, First Out):

A última função chamada é a primeira a retornar
Cada chamada recursiva empilha seu contexto (parâmetros, variáveis locais, endereço de retorno)
Quando uma função termina, desempilha e retorna para a chamada anterior

Exemplo:

fibonacci(4)
├─ fibonacci(3) + fibonacci(2)
│  ├─ fibonacci(2) + fibonacci(1)
│  │  ├─ fibonacci(1) + fibonacci(0)
│  │  └─ retorna...
│  └─ retorna...
└─ retorna resultado final

Por que as outras opções não funcionam:

2. Array:

Não tem semântica natural de empilhar/desempilhar
Requer gerenciamento manual de índices
Não segue automaticamente LIFO

3. Lista:

Dependendo da implementação, pode não ser eficiente para operações LIFO
Inserção/remoção no meio ou início pode ser custosa

4. Fila (Queue):

Segue FIFO (First In, First Out), que é o oposto do necessário
A primeira chamada sairia primeiro, quebrando a lógica recursiva

Conclusão: Stack é a estrutura natural para recursão, tanto que os sistemas operacionais usam uma “pilha de execução” (call stack) para gerenciar chamadas de função automaticamente.

5. Melhor Uso para uma Árvore

As árvores têm diversos usos importantes na ciência da computação. Aqui estão os principais:

Busca e organização de dados:

Árvores de busca binária (BST): Para busca eficiente em O(log n)
Árvores AVL/Red-Black: Busca balanceada garantida
B-trees: Índices de bancos de dados e sistemas de arquivos

Análise sintática e compiladores:

Árvores sintáticas: Representar estrutura de código fonte
Árvores de expressões: Avaliar expressões matemáticas
AST (Abstract Syntax Tree): Compiladores e interpretadores

Hierarquias e estruturas organizacionais:

Árvores de diretórios: Sistemas de arquivos
Árvores genealógicas: Relacionamentos familiares
Estruturas organizacionais: Hierarquias empresariais
Categorização: Taxonomias e classificações

Algoritmos e otimização:

Árvores de decisão: Machine learning e IA
Heaps: Filas de prioridade e algoritmos como Dijkstra
Árvore de Prefixo (Tries): Autocompletar e busca de strings
Árvores de Huffman: Compressão de dados

Interfaces gráficas:

DOM: Estrutura de páginas web
Árvores de componentes: Frameworks como React
Menus hierárquicos: Interfaces de usuário

Redes e comunicação:

Árvores spanning: Redes de computadores
Routing trees: Protocolos de rede

O “melhor uso” depende do contexto específico, mas árvores são ideais sempre que você precisa de estrutura hierárquica, busca eficiente ou representação de relacionamentos pai-filho.

6. Complexidade de Inserção em Árvore Balanceada

Pergunta: No pior dos casos, qual a complexidade para inserir em árvore balanceada?

No pior dos casos, a complexidade para inserir em uma árvore balanceada é O(log n).

Por que O(log n):

Altura garantida: Árvores balanceadas (AVL, Red-Black, etc.) mantêm altura máxima de O(log n)
Caminho de inserção: A inserção percorre um caminho da raiz até uma folha
Operações de balanceamento: Mesmo com rotações para manter o balanceamento, essas operações são O(1) e limitadas

Exemplos de árvores balanceadas:

Árvore AVL:

Altura máxima: ~1.44 × log₂(n)
Inserção + rebalanceamento: O(log n)

Red-Black Tree:

Altura máxima: 2 × log₂(n)
Inserção + correção de cores: O(log n)

B-Tree:

Altura: O(log_m n), onde m é a ordem da árvore
Inserção + possível split: O(log n)

Contraste com árvore não balanceada:

BST degenerada: pode ter altura O(n) no pior caso
Árvore balanceada: sempre mantém altura O(log n)

O balanceamento garante que mesmo no pior cenário, a inserção nunca exceda O(log n), que é uma das principais vantagens dessas estruturas sobre árvores binárias simples.

Referências

Projeto de Algorítmos - com Implementação em Pascal e C, Ph.D. Nivio Ziviani, ed. 2011 ↩︎
Entendendo Algorítmos, Aditya Bhargava, ed. 2017 ↩︎
Data Structures and Algorithms (DSA), disponível em https://www.geeksforgeeks.org/dsa/dsa-tutorial-learn-data-structures-and-algorithms ↩︎
Learning Data Structures and Algorithms Course, by Rod Stephens, O’Reilly Learning, disponível em https://learning.oreilly.com/course/learning-data-structures/9781771373470/ ↩︎

Adriano Vieira