Complexidade de algoritmos: da teoria à medição na prática
Complexidade de algoritmos é o estudo de quantos recursos (principalmente tempo e memória) um algoritmo consome em função do tamanho da entrada. Em vez de perguntar “quantos segundos este programa leva?”, perguntamos “como o custo cresce quando a entrada dobra, quadruplica ou fica mil vezes maior?”. Essa pergunta é mais útil porque a resposta não depende do computador, da linguagem ou do compilador (Cormen et al., 2022; Sedgewick; Wayne, 2011).
Ao longo deste artigo usaremos um único problema: o sistema de inscrições de um evento acadêmico recebe uma lista de números de matrícula e precisa saber se alguma matrícula aparece repetida. Resolveremos o problema de três maneiras, analisaremos cada uma na teoria e depois confrontaremos a teoria com contagens e medições reais em C++17. Em seguida, usaremos a mesma lente para revisitar as estruturas e algoritmos que você já estudou (ordenações, buscas, pilhas, filas, listas e árvores) e entender por que cada uma custa o que custa.
Ao final você deverá ser capaz de:
- explicar por que contamos operações em vez de segundos;
- classificar um trecho de código em O(1), O(log n), O(n), O(n log n) ou O(n²);
- distinguir pior caso, melhor caso e caso médio;
- verificar na prática se uma análise teórica se confirma;
- usar a complexidade para explicar o desempenho de ordenações, buscas, pilhas, filas, listas e árvores, e escolher entre elas.
Fundamentos: o que medir e como
Tamanho da entrada e operação básica
Para comparar algoritmos precisamos de duas escolhas:
- Tamanho da entrada (n): no nosso problema, o número de matrículas na lista.
- Operação básica: a operação que mais pesa no custo e que se repete. Aqui, a comparação entre duas matrículas.
A complexidade de tempo é então uma função T(n) que conta quantas vezes a operação básica ocorre. Contar operações tem uma vantagem: o resultado é o mesmo em qualquer máquina. Já o tempo em segundos muda de computador para computador.
Notação assintótica
Como T(n) exata costuma ser trabalhosa, e detalhes como somas de constantes pouco importam quando n é grande, usamos a notação assintótica, que descreve a taxa de crescimento (Knuth, 1976; Cormen et al., 2022).
Definição (O, “limite superior”). Dizemos que T(n) = O(g(n)) se existem constantes positivas c e n₀ tais que
T(n) ≤ c · g(n) para todo n ≥ n₀.
Lê-se: “a partir de certo tamanho, T(n) nunca cresce mais rápido que um múltiplo de g(n)”.
Exemplo. Seja T(n) = 3n² + 5n + 2. Para n ≥ 1 temos 5n ≤ 5n² e 2 ≤ 2n², logo
3n² + 5n + 2 ≤ 3n² + 5n² + 2n² = 10n².
Tomando c = 10 e n₀ = 1, concluímos que T(n) = O(n²). Note como o termo dominante (n²) decide a classe e as constantes são “absorvidas”.
Há duas notações complementares:
| Notação | Significado informal | Ideia |
|---|---|---|
| O(g(n)) | cresce no máximo como g(n) | limite superior |
| Ω(g(n)) | cresce no mínimo como g(n) | limite inferior |
| Θ(g(n)) | cresce exatamente como g(n), a menos de constantes | limite justo (O e Ω juntos) |
No dia a dia é comum dizer “O(n²)” querendo dizer Θ(n²). Neste artigo, quando houver diferença, ela será explicitada.
As classes mais comuns
| Classe | Nome | Exemplo típico | Se n dobra, o custo… |
|---|---|---|---|
| O(1) | constante | acessar v[i] | não muda |
| O(log n) | logarítmica | busca binária | aumenta em uma unidade fixa |
| O(n) | linear | achar o maior elemento | dobra |
| O(n log n) | linearítmica | ordenação eficiente | pouco mais que dobra |
| O(n²) | quadrática | dois laços aninhados | quadruplica |
| O(2ⁿ) | exponencial | testar todos os subconjuntos | é elevado ao quadrado |
Essas classes estão em ordem crescente de custo. Entre O(n log n) e O(n²) há um abismo para n grande, como veremos.
Melhor, pior e caso médio
Para a mesma entrada de tamanho n, o custo pode variar conforme o conteúdo da entrada. Por exemplo, se a primeira matrícula for igual à segunda, uma busca por duplicata termina na hora. Por isso falamos em:
- melhor caso: a entrada mais favorável;
- pior caso: a mais desfavorável, que dá uma garantia de que o algoritmo nunca fará pior;
- caso médio: o custo esperado sobre uma distribuição de entradas (exige hipóteses probabilísticas).
Por padrão, a análise de pior caso é a mais usada, porque é uma garantia. Em todos os experimentos abaixo forçamos o pior caso: todas as matrículas são distintas, de modo que nenhum algoritmo consegue parar antes do fim.
Análise teórica do nosso problema
Versão A: comparar todos os pares
A ideia mais direta é comparar cada matrícula com todas as seguintes.
bool temDuplicataQuadratica(const vector<int>& matriculas, long long& comparacoes) {
int n = matriculas.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
comparacoes++;
if (matriculas[i] == matriculas[j]) {
return true;
}
}
}
return false;
}No pior caso, o laço interno executa (n − 1) vezes para i = 0, (n − 2) para i = 1, e assim por diante até 0. A soma é
(n − 1) + (n − 2) + … + 1 + 0 = n(n − 1)/2 = n²/2 − n/2.
Logo T(n) = Θ(n²). Por exemplo, para n = 1000 esperamos 1000 · 999 / 2 = 499.500 comparações. O melhor caso é O(1) (duplicata nas duas primeiras posições).
Versão B: ordenar e olhar os vizinhos
Se a lista estiver ordenada, matrículas iguais ficam lado a lado. Basta então ordenar e comparar cada elemento com o anterior.
bool temDuplicataOrdenando(vector<int> matriculas, long long& comparacoes) {
// O terceiro argumento do sort conta cada comparação feita pela ordenação.
sort(matriculas.begin(), matriculas.end(), [&comparacoes](int a, int b) {
comparacoes++;
return a < b;
});
for (size_t i = 1; i < matriculas.size(); i++) {
comparacoes++;
if (matriculas[i] == matriculas[i - 1]) {
return true;
}
}
return false;
}O parâmetro é recebido por valor, ou seja, o sort trabalha numa cópia e não bagunça a lista original. O trecho [&comparacoes](int a, int b) { ... } é apenas uma pequena função sem nome que o sort chama para comparar dois elementos; nós a usamos só para contar quantas vezes isso acontece.
O padrão C++ exige que std::sort faça O(n log n) comparações (ISO/IEC, 2017). O laço final custa n − 1 comparações, que é menor, e portanto a soma é dominada pela ordenação: T(n) = O(n log n). O preço é a cópia da lista, isto é, memória extra O(n).
Um laço simples para comparar: o maior valor
Como referência de custo linear, considere achar a maior matrícula:
int maiorMatricula(const vector<int>& matriculas, long long& comparacoes) {
int maior = matriculas[0];
for (size_t i = 1; i < matriculas.size(); i++) {
comparacoes++;
if (matriculas[i] > maior) {
maior = matriculas[i];
}
}
return maior;
}Há exatamente n − 1 comparações, sempre, e portanto Θ(n).
Regras práticas para analisar código
- Uma sequência de instruções simples custa O(1).
- Um laço que vai de 1 a n, com corpo O(1), custa O(n).
- Laços aninhados multiplicam: dois laços até n resultam em O(n²).
- Instruções em sequência somam, e vale o maior termo: O(n) + O(n²) = O(n²).
- Se a cada passo o problema cai pela metade, o número de passos é cerca de log₂ n.
A regra 5 aparece na busca binária, que veremos adiante.
Colocando a teoria à prova: contando operações
O programa abaixo é completo. Ele gera listas de matrículas distintas, embaralhadas com semente fixa para reprodutibilidade, e conta as comparações das três funções vistas acima para n = 1000, 2000, …, 16000.
#include <algorithm>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>
using namespace std;
// Versão A: compara todos os pares (i, j). Força bruta.
bool temDuplicataQuadratica(const vector<int>& matriculas, long long& comparacoes) {
int n = matriculas.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
comparacoes++;
if (matriculas[i] == matriculas[j]) {
return true;
}
}
}
return false;
}
// Versão B: ordena uma cópia e olha apenas vizinhos.
bool temDuplicataOrdenando(vector<int> matriculas, long long& comparacoes) {
// O terceiro argumento do sort conta cada comparação feita pela ordenação.
sort(matriculas.begin(), matriculas.end(), [&comparacoes](int a, int b) {
comparacoes++;
return a < b;
});
for (size_t i = 1; i < matriculas.size(); i++) {
comparacoes++;
if (matriculas[i] == matriculas[i - 1]) {
return true;
}
}
return false;
}
// Um laço simples: encontra a maior matrícula. Custo linear.
int maiorMatricula(const vector<int>& matriculas, long long& comparacoes) {
int maior = matriculas[0];
for (size_t i = 1; i < matriculas.size(); i++) {
comparacoes++;
if (matriculas[i] > maior) {
maior = matriculas[i];
}
}
return maior;
}
int main() {
mt19937 gerador(42); // semente fixa: resultados reproduzíveis
cout << " n | maior (n-1) | duplicata A (n^2) | duplicata B (n log n)\n";
for (int n = 1000; n <= 16000; n *= 2) {
// Pior caso: matrículas todas distintas, então nenhuma versão para antes do fim.
vector<int> matriculas(n);
iota(matriculas.begin(), matriculas.end(), 1000);
shuffle(matriculas.begin(), matriculas.end(), gerador);
long long cMaior = 0, cA = 0, cB = 0;
maiorMatricula(matriculas, cMaior);
temDuplicataQuadratica(matriculas, cA);
temDuplicataOrdenando(matriculas, cB);
cout.width(7); cout << n << " | ";
cout.width(11); cout << cMaior << " | ";
cout.width(17); cout << cA << " | ";
cout.width(21); cout << cB << "\n";
}
return 0;
}Compilação e execução (g++ 16.2.1, -std=c++17 -O2 -Wall -Wextra):
n | maior (n-1) | duplicata A (n^2) | duplicata B (n log n)
1000 | 999 | 499500 | 13125
2000 | 1999 | 1999000 | 28027
4000 | 3999 | 7998000 | 64086
8000 | 7999 | 31996000 | 131111
16000 | 15999 | 127992000 | 284477(O valor exato da coluna B pode variar entre implementações da biblioteca padrão; a tendência de crescimento é a que importa.)
Lendo os números
- Coluna “maior”: sempre n − 1, exatamente como previsto. Dobrar n dobra o custo.
- Coluna A: para n = 1000, 499.500, exatamente o valor n(n − 1)/2 calculado na teoria. Quando n dobra de 1000 para 2000, o custo vai de 499.500 para 1.999.000, um fator de aproximadamente 4. De 8000 para 16000, de 31.996.000 para 127.992.000, de novo fator 4. É a assinatura do crescimento quadrático.
- Coluna B: dobrar n multiplica o custo por cerca de 2,05 a 2,3 (por exemplo, 131.111 para 284.477), ligeiramente acima de 2. É a assinatura do n log n: como log n também cresce devagar, o custo “pouco mais que dobra”.
Observe a distância entre as colunas em n = 16000: 127,9 milhões contra 284 mil de comparações, uma razão de cerca de 450 vezes, e ela só aumenta com n.
Teoria e prática: o logaritmo em ação
Para ver O(log n) de perto, voltemos a uma operação que a secretaria do evento faz o tempo todo: procurar uma matrícula numa lista já ordenada. Comparamos a busca sequencial (O(n)) com a binária (O(log n)). A binária compara o alvo com o elemento do meio e descarta metade da lista a cada passo.
Se T(n) é o custo para n elementos, então T(n) = T(n/2) + 1, pois fazemos uma comparação e recaímos num problema com metade do tamanho. Dividindo n por 2 repetidamente, chegamos a 1 após cerca de log₂ n passos, e portanto T(n) = O(log n) (Cormen et al., 2022).
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
// Percorre a lista do início ao fim. No pior caso, n comparações.
int buscaSequencial(const vector<int>& v, int alvo, int& comparacoes) {
for (int i = 0; i < (int)v.size(); i++) {
comparacoes++;
if (v[i] == alvo) {
return i;
}
}
return -1;
}
// Exige lista ordenada. A cada passo descarta metade: cerca de log2(n) comparações.
int buscaBinaria(const vector<int>& v, int alvo, int& comparacoes) {
int inicio = 0, fim = (int)v.size() - 1;
while (inicio <= fim) {
int meio = inicio + (fim - inicio) / 2;
comparacoes++;
if (v[meio] == alvo) {
return meio;
} else if (v[meio] < alvo) {
inicio = meio + 1;
} else {
fim = meio - 1;
}
}
return -1;
}
int main() {
cout << " n | sequencial (pior caso) | binária (pior caso)\n";
for (int n = 1000; n <= 1000000; n *= 10) {
vector<int> v(n);
iota(v.begin(), v.end(), 0); // 0, 1, ..., n-1 já ordenado
int cSeq = 0, cBin = 0;
buscaSequencial(v, -1, cSeq); // -1 não existe: força o pior caso
buscaBinaria(v, -1, cBin);
cout.width(9); cout << n << " | ";
cout.width(22); cout << cSeq << " | ";
cout.width(19); cout << cBin << "\n";
}
return 0;
}Saída obtida:
n | sequencial (pior caso) | binária (pior caso)
1000 | 1000 | 9
10000 | 10000 | 13
100000 | 100000 | 16
1000000 | 1000000 | 19Multiplicar n por 10 multiplica por 10 a busca sequencial, mas soma apenas cerca de 3,3 (log₂ 10) à binária. Para um milhão de matrículas, são 19 comparações contra 1.000.000. Repare também na condição: a busca binária só funciona se a lista estiver ordenada, e essa preparação tem custo (O(n log n) para ordenar). Se for buscar uma única vez, ordenar antes não compensa; se for buscar muitas vezes, compensa muito.
Medindo o tempo real
Contar operações é limpo, mas o que o usuário sente é o tempo. Vamos medir com std::chrono, agora incluindo uma terceira versão, que usa um conjunto de dispersão (unordered_set): percorre a lista e, para cada matrícula, pergunta se ela já foi vista. Cada consulta e inserção custa O(1) em média, de modo que a versão tem custo esperado O(n) (Cormen et al., 2022). Note o “em média”: no pior caso teórico, as operações de um conjunto de dispersão podem degradar, e é por isso que a classificação como O(n) vale para o caso médio, não como garantia.
#include <algorithm>
#include <chrono>
#include <iostream>
#include <numeric>
#include <random>
#include <unordered_set>
#include <vector>
using namespace std;
using namespace std::chrono;
bool temDuplicataQuadratica(const vector<int>& matriculas) {
int n = matriculas.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (matriculas[i] == matriculas[j]) {
return true;
}
}
}
return false;
}
bool temDuplicataOrdenando(vector<int> matriculas) {
sort(matriculas.begin(), matriculas.end());
for (size_t i = 1; i < matriculas.size(); i++) {
if (matriculas[i] == matriculas[i - 1]) {
return true;
}
}
return false;
}
// Versão C: conjunto de hash. Custo esperado linear (caso médio).
bool temDuplicataComConjunto(const vector<int>& matriculas) {
unordered_set<int> vistas;
for (int m : matriculas) {
if (vistas.count(m) > 0) {
return true;
}
vistas.insert(m);
}
return false;
}
// Mede em milissegundos o tempo de uma chamada à função recebida.
template <typename Funcao>
double medirMs(Funcao f, const vector<int>& dados) {
auto inicio = steady_clock::now();
bool resultado = f(dados);
auto fim = steady_clock::now();
if (resultado) {
cout << "(inesperado: duplicata encontrada)\n";
}
return duration<double, milli>(fim - inicio).count();
}
int main() {
mt19937 gerador(42);
cout << " n | A: n^2 (ms) | B: n log n (ms) | C: hash (ms)\n";
for (int n = 2000; n <= 64000; n *= 2) {
vector<int> matriculas(n);
iota(matriculas.begin(), matriculas.end(), 1000);
shuffle(matriculas.begin(), matriculas.end(), gerador);
double tA = medirMs(temDuplicataQuadratica, matriculas);
double tB = medirMs(temDuplicataOrdenando, matriculas);
double tC = medirMs(temDuplicataComConjunto, matriculas);
cout.width(7); cout << n << " | ";
cout.width(13); cout << tA << " | ";
cout.width(15); cout << tB << " | ";
cout.width(12); cout << tC << "\n";
}
return 0;
}Resultado (AMD Ryzen 7 5700U, Linux, g++ 16.2.1, -std=c++17 -O2; um único experimento por tamanho):
n | A: n^2 (ms) | B: n log n (ms) | C: hash (ms)
2000 | 0.989366 | 0.141987 | 0.246608
4000 | 4.01061 | 0.282437 | 0.411852
8000 | 16.0392 | 0.596371 | 0.857996
16000 | 62.088 | 1.27411 | 1.75727
32000 | 249.012 | 2.78512 | 3.81373
64000 | 998.445 | 5.82362 | 8.11286Seus tempos serão diferentes: dependem da máquina, da carga do sistema e do compilador. O que deve se repetir é a forma do crescimento:
- A: cada duplicação de n multiplica o tempo por cerca de 4 (0,99 → 4,0 → 16,0 → 62,1 → 249,0 → 998,4 ms). Quadrático, como a teoria previu. Com 64.000 matrículas, já é perto de 1 segundo, e para 640.000 o tempo estimado seria cerca de 100 segundos.
- B: o tempo pouco mais que dobra a cada duplicação (0,14 → 0,28 → 0,60 → 1,27 → 2,79 → 5,82 ms).
- C: cresce quase linearmente (0,25 → 0,41 → 0,86 → 1,76 → 3,81 → 8,11 ms), mas, nestes tamanhos, é mais lenta que a B.
O que a prática ensina sobre a teoria
O último ponto merece atenção: a versão C tem melhor classe assintótica (O(n) em média contra O(n log n)), e mesmo assim perdeu a corrida neste experimento. Isso não contradiz a teoria. A notação assintótica ignora constantes e descreve o comportamento quando n tende ao infinito. O conjunto de dispersão aloca memória para cada elemento e acessa posições dispersas da memória, o que tem um custo constante grande, enquanto o sort trabalha sobre um vetor contíguo. Em tamanhos muito maiores a vantagem assintótica tende a aparecer, mas isso depende do hardware e deve ser medido, não presumido.
A complexidade por trás das estruturas e algoritmos clássicos
Tudo o que vimos até aqui se aplica diretamente às estruturas de dados que você já estudou. Cada estrutura é, na prática, uma escolha de quais operações serão baratas e quais serão caras. A análise de complexidade é a ferramenta que torna essa escolha explícita (Cormen et al., 2022; Sedgewick; Wayne, 2011).
Tabela de referência
As tabelas abaixo resumem os custos usuais. Elas são o ponto de partida; nas subseções seguintes verificamos várias delas em código. Em todas, n é o número de elementos e os custos são de tempo, exceto onde indicado.
Algoritmos de ordenação
| Algoritmo | Melhor caso | Caso médio | Pior caso | Memória extra | Observação |
|---|---|---|---|---|---|
| Seleção | Θ(n²) | Θ(n²) | Θ(n²) | O(1) | faz o mesmo trabalho mesmo se a lista já estiver ordenada |
| Inserção | Θ(n) | Θ(n²) | Θ(n²) | O(1) | ótima para listas quase ordenadas ou pequenas |
| Bolha (com parada antecipada) | Θ(n) | Θ(n²) | Θ(n²) | O(1) | didática; raramente usada na prática |
| Intercalação (merge sort) | Θ(n log n) | Θ(n log n) | Θ(n log n) | O(n) | custo previsível, usa vetor auxiliar |
| Quicksort | Θ(n log n) | Θ(n log n) | Θ(n²) | O(log n) | pior caso raro com boa escolha do pivô |
| Heapsort | Θ(n log n) | Θ(n log n) | Θ(n log n) | O(1) | ordena sobre o próprio vetor |
std::sort (C++) | — | — | O(n log n) | — | o padrão da linguagem exige O(n log n) comparações |
Algoritmos de busca
| Algoritmo | Melhor caso | Caso médio | Pior caso | Pré-requisito |
|---|---|---|---|---|
| Sequencial | O(1) | O(n) | O(n) | nenhum |
| Binária (em vetor) | O(1) | O(log n) | O(log n) | vetor ordenado |
| Tabela de dispersão (hash) | O(1) | O(1) | O(n) | boa função de dispersão |
| Árvore binária de busca | O(1) | O(log n) | O(n) | depende do formato da árvore |
| Árvore balanceada (AVL, rubro-negra) | O(1) | O(log n) | O(log n) | rebalanceamento a cada inserção |
Estruturas lineares e árvores: custo de cada operação
| Estrutura | Inserir | Remover | Acessar / buscar | Comentário |
|---|---|---|---|---|
Pilha (em vector) | O(1)* | O(1) | topo: O(1) | só se mexe no fim; *push_back é O(1) amortizado |
Fila ingênua (em vector) | O(1)* | O(n) | frente: O(1) | remover do início desloca todos os elementos |
| Fila com índice de início | O(1)* | O(1) | frente: O(1) | não desloca nada; desperdiça espaço dos removidos |
Lista como vector | início: O(n); fim: O(1)* | início: O(n) | posição: O(1); valor: O(n) | memória contígua |
| Lista encadeada | início: O(1) | início: O(1) | posição: O(n); valor: O(n) | cada nó aponta para o próximo |
| Árvore binária de busca | O(h) | O(h) | O(h) | h = altura: de O(log n) a O(n) |
| Árvore balanceada | O(log n) | O(log n) | O(log n) | h é garantidamente O(log n) |
| Heap binário | O(log n) | min/máx: O(log n) | min/máx: O(1) | base de filas de prioridade |
A leitura da tabela é sempre a mesma: não existe estrutura “a melhor”. A lista encadeada insere no início em O(1), mas perde em acesso por posição; o vector faz o oposto. O restante da seção mostra isso em números.
Ordenação: o melhor, o médio e o pior caso aparecem de verdade
A ordenação por inserção é uma boa vitrine dos três casos: em lista já ordenada, cada elemento é comparado uma única vez (n − 1 comparações no total); em lista inversa, cada elemento precisa passar por todos os anteriores (n(n − 1)/2); em lista embaralhada, em média metade disso, ou seja, cerca de n²/4. Comparamos com a ordenação por intercalação, que divide a lista ao meio, ordena cada metade e intercala. Como há cerca de log₂ n níveis de divisão e cada nível custa no máximo n comparações para intercalar, o total é O(n log n) em qualquer caso (Cormen et al., 2022).
#include <algorithm>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>
using namespace std;
// Ordenação por inserção: pega cada elemento e o "empurra" para a posição certa.
long long ordenacaoInsercao(vector<int> v) {
long long comparacoes = 0;
for (size_t i = 1; i < v.size(); i++) {
int chave = v[i];
int j = (int)i - 1;
while (j >= 0) {
comparacoes++;
if (v[j] <= chave) {
break;
}
v[j + 1] = v[j];
j--;
}
v[j + 1] = chave;
}
return comparacoes;
}
// Intercala as duas metades já ordenadas v[inicio..meio) e v[meio..fim).
void intercalar(vector<int>& v, vector<int>& aux, int inicio, int meio, int fim,
long long& comparacoes) {
int i = inicio, j = meio, k = inicio;
while (i < meio && j < fim) {
comparacoes++;
if (v[i] <= v[j]) {
aux[k++] = v[i++];
} else {
aux[k++] = v[j++];
}
}
while (i < meio) aux[k++] = v[i++];
while (j < fim) aux[k++] = v[j++];
for (k = inicio; k < fim; k++) v[k] = aux[k];
}
// Ordenação por intercalação: divide ao meio, ordena cada metade e intercala.
void ordenacaoIntercalacao(vector<int>& v, vector<int>& aux, int inicio, int fim,
long long& comparacoes) {
if (fim - inicio < 2) {
return;
}
int meio = inicio + (fim - inicio) / 2;
ordenacaoIntercalacao(v, aux, inicio, meio, comparacoes);
ordenacaoIntercalacao(v, aux, meio, fim, comparacoes);
intercalar(v, aux, inicio, meio, fim, comparacoes);
}
int main() {
mt19937 gerador(42);
cout << " n | insercao: melhor | insercao: medio | insercao: pior | intercalacao\n";
for (int n = 1000; n <= 8000; n *= 2) {
vector<int> crescente(n);
iota(crescente.begin(), crescente.end(), 0);
vector<int> decrescente(crescente.rbegin(), crescente.rend());
vector<int> aleatoria = crescente;
shuffle(aleatoria.begin(), aleatoria.end(), gerador);
long long cMelhor = ordenacaoInsercao(crescente);
long long cMedio = ordenacaoInsercao(aleatoria);
long long cPior = ordenacaoInsercao(decrescente);
vector<int> copia = aleatoria;
vector<int> aux(n);
long long cInter = 0;
ordenacaoIntercalacao(copia, aux, 0, n, cInter);
cout.width(7); cout << n << " | ";
cout.width(16); cout << cMelhor << " | ";
cout.width(15); cout << cMedio << " | ";
cout.width(14); cout << cPior << " | ";
cout.width(12); cout << cInter << "\n";
}
return 0;
}Saída obtida:
n | insercao: melhor | insercao: medio | insercao: pior | intercalacao
1000 | 999 | 246352 | 499500 | 8713
2000 | 1999 | 997538 | 1999000 | 19408
4000 | 3999 | 3978974 | 7998000 | 42809
8000 | 7999 | 16107630 | 31996000 | 93663Conferindo com a teoria:
- Melhor caso: n − 1 exatamente (999, 1999, …). Custo linear.
- Pior caso: n(n − 1)/2 exatamente (499.500 para n = 1000). Custo quadrático.
- Caso médio: 246.352 para n = 1000, bem próximo de n²/4 = 250.000. O crescimento também é quadrático: dobrar n multiplica o custo por cerca de 4.
- Intercalação: 8.713 comparações para n = 1000, abaixo de n log₂ n ≈ 9.966, e dobrar n pouco mais que dobra o custo. Para n = 8000, a inserção em média faz 16,1 milhões de comparações contra 93,6 mil da intercalação, algo como 170 vezes mais.
A lição vai além da ordenação: o mesmo algoritmo pode ser excelente ou péssimo conforme os dados. Por isso, antes de escolher, pergunte como é a entrada típica (quase ordenada? aleatória?). A intercalação, em compensação, paga com memória: o vetor auxiliar aux torna sua memória extra O(n).
Pilhas, filas e listas: o custo está em onde se mexe
Voltemos à secretaria do evento. Os inscritos entram numa fila de atendimento, os atendimentos desfeitos são guardados numa pilha (o último a ser feito é o primeiro a ser desfeito) e a lista de presença é uma lista. O programa a seguir conta os “passos” (uma inserção, uma remoção ou um elemento deslocado conta um passo) de operações sobre n elementos.
#include <iostream>
#include <vector>
using namespace std;
int main() {
cout << " n | pilha (2n) | fila ingenua | fila c/ indice | insere inicio: vector | insere inicio: lista\n";
for (int n = 1000; n <= 8000; n *= 2) {
// ---- Pilha: empilhar e desempilhar só mexem no fim do vector ----
long long passosPilha = 0;
vector<int> pilha;
for (int i = 0; i < n; i++) { pilha.push_back(i); passosPilha++; }
while (!pilha.empty()) { pilha.pop_back(); passosPilha++; }
// ---- Fila ingênua: desenfileirar remove o primeiro e desloca todos os outros ----
long long passosFilaIngenua = 0;
vector<int> fila;
for (int i = 0; i < n; i++) { fila.push_back(i); passosFilaIngenua++; }
while (!fila.empty()) {
passosFilaIngenua += (long long)fila.size() - 1; // elementos deslocados
fila.erase(fila.begin());
passosFilaIngenua++;
}
// ---- Fila com índice: só avançamos o índice do início, sem deslocar nada ----
long long passosFilaIndice = 0;
vector<int> fila2;
size_t inicio = 0;
for (int i = 0; i < n; i++) { fila2.push_back(i); passosFilaIndice++; }
while (inicio < fila2.size()) { inicio++; passosFilaIndice++; }
// ---- Lista como vector: inserir no início desloca todos os elementos ----
long long passosVector = 0;
vector<int> lista;
for (int i = 0; i < n; i++) {
passosVector += (long long)lista.size() + 1; // deslocamentos + a inserção
lista.insert(lista.begin(), i);
}
// ---- Lista encadeada (por índices): inserir no início é só trocar a cabeça ----
long long passosEncadeada = 0;
vector<int> valor, proximo;
int cabeca = -1;
for (int i = 0; i < n; i++) {
valor.push_back(i);
proximo.push_back(cabeca); // o novo nó aponta para o antigo primeiro
cabeca = (int)valor.size() - 1;
passosEncadeada++;
}
cout.width(7); cout << n << " | ";
cout.width(10); cout << passosPilha << " | ";
cout.width(12); cout << passosFilaIngenua << " | ";
cout.width(14); cout << passosFilaIndice << " | ";
cout.width(21); cout << passosVector << " | ";
cout.width(20); cout << passosEncadeada << "\n";
}
// ---- Acesso ao k-ésimo elemento: vector vs lista encadeada ----
cout << "\n n | acesso ao ultimo: vector | acesso ao ultimo: lista\n";
for (int n = 1000; n <= 8000; n *= 2) {
vector<int> valor(n), proximo(n);
for (int i = 0; i < n; i++) {
valor[i] = i;
proximo[i] = (i + 1 < n) ? i + 1 : -1;
}
long long passosVector = 1; // valor[n-1]
long long passosLista = 0;
int atual = 0; // cabeça = nó 0
while (proximo[atual] != -1) { atual = proximo[atual]; passosLista++; }
cout.width(7); cout << n << " | ";
cout.width(24); cout << passosVector << " | ";
cout.width(23); cout << passosLista << "\n";
}
return 0;
}Saída obtida:
n | pilha (2n) | fila ingenua | fila c/ indice | insere inicio: vector | insere inicio: lista
1000 | 2000 | 501500 | 2000 | 500500 | 1000
2000 | 4000 | 2003000 | 4000 | 2001000 | 2000
4000 | 8000 | 8006000 | 8000 | 8002000 | 4000
8000 | 16000 | 32012000 | 16000 | 32004000 | 8000
n | acesso ao ultimo: vector | acesso ao ultimo: lista
1000 | 1 | 999
2000 | 1 | 1999
4000 | 1 | 3999
8000 | 1 | 7999O que os números mostram:
- Pilha: 2n passos para n empilhamentos e n desempilhamentos. Cada operação é O(1), pois só toca no fim do
vector. - Fila ingênua (desenfileirar com
erase(begin())): cerca de n²/2 passos, o mesmo crescimento quadrático do pior caso da inserção. Cada remoção desloca todos os outros elementos para a esquerda. - Fila com índice de início: de novo 2n passos. Basta avançar um índice em vez de deslocar. A troca é que o espaço dos elementos já removidos continua ocupado até o fim. Filas circulares e a
std::queueresolvem isso, mas a ideia de custo é a mesma: remover da frente em O(1). - Lista como
vectorvs. lista encadeada: inserir n elementos no início custa cerca de n²/2 deslocamentos novector(32 milhões para n = 8000) e apenas n passos na lista encadeada, que só precisa mudar a “cabeça”. Em contrapartida, chegar ao último elemento custa 1 passo novectore n − 1 passos na lista encadeada. Essa é a troca fundamental entre as duas estruturas.
Na lista encadeada do código, cada “nó” é uma posição nos vetores valor e proximo, e proximo[i] guarda o índice do nó seguinte (−1 quando não há). Isso reproduz a ideia de ponteiros sem precisar de alocação dinâmica.
Um detalhe sobre push_back: quando o vector fica cheio, ele aloca um espaço maior e copia tudo, um custo O(n) naquela chamada. Como isso acontece cada vez menos vezes à medida que o vetor cresce, o custo médio por inserção no fim é constante. Dizemos que push_back é O(1) amortizado; a demonstração formal fica para estudos posteriores (Cormen et al., 2022).
Árvores: a altura decide tudo
Em uma árvore binária de busca, cada comparação com a chave de um nó descarta uma subárvore. Buscar, inserir e remover custam O(h), em que h é a altura da árvore (o número de níveis do caminho mais longo). Se a árvore for “equilibrada”, h ≈ log₂ n e tudo é logarítmico. Se ela degenerar numa corrente de nós, h = n e voltamos à busca sequencial (Cormen et al., 2022). O programa abaixo guarda a árvore em vetores (o nó i tem chave[i], esquerda[i] e direita[i]) e insere as mesmas chaves de duas maneiras: em ordem crescente e em ordem embaralhada.
#include <algorithm>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>
using namespace std;
// Árvore binária de busca guardada em vetores: o nó i tem chave[i],
// filho esquerdo esquerda[i] e filho direito direita[i] (-1 = não existe).
vector<int> chave, esquerda, direita;
// Insere e devolve quantas comparações foram feitas para achar o lugar.
int inserir(int valor) {
int comparacoes = 0;
chave.push_back(valor);
esquerda.push_back(-1);
direita.push_back(-1);
int novo = (int)chave.size() - 1;
if (novo == 0) {
return 0; // primeira chave vira a raiz
}
int atual = 0;
while (true) {
comparacoes++;
if (valor < chave[atual]) {
if (esquerda[atual] == -1) { esquerda[atual] = novo; break; }
atual = esquerda[atual];
} else {
if (direita[atual] == -1) { direita[atual] = novo; break; }
atual = direita[atual];
}
}
return comparacoes;
}
// Altura da árvore a partir do nó dado: número de níveis do caminho mais longo.
int altura(int no) {
if (no == -1) {
return 0;
}
return 1 + max(altura(esquerda[no]), altura(direita[no]));
}
// Quantas comparações a busca por um valor faz (-1 em filho = não achou).
int buscar(int valor) {
int comparacoes = 0;
int atual = 0;
while (atual != -1) {
comparacoes++;
if (valor == chave[atual]) {
break;
}
atual = (valor < chave[atual]) ? esquerda[atual] : direita[atual];
}
return comparacoes;
}
void limpar() {
chave.clear();
esquerda.clear();
direita.clear();
}
int main() {
mt19937 gerador(42);
cout << " n | ordem crescente: altura / busca do ultimo | ordem aleatoria: altura / busca do ultimo\n";
for (int n = 500; n <= 4000; n *= 2) {
vector<int> valores(n);
iota(valores.begin(), valores.end(), 1);
// Degenerada: chaves chegam em ordem crescente, a árvore vira uma "lista".
limpar();
for (int v : valores) inserir(v);
int altCrescente = altura(0);
int buscaCrescente = buscar(n);
// Aleatória: a mesma coleção, mas inserida em ordem embaralhada.
shuffle(valores.begin(), valores.end(), gerador);
limpar();
for (int v : valores) inserir(v);
int altAleatoria = altura(0);
int buscaAleatoria = buscar(valores.back());
cout.width(7); cout << n << " | ";
cout.width(22); cout << altCrescente;
cout << " /";
cout.width(5); cout << buscaCrescente << " | ";
cout.width(22); cout << altAleatoria;
cout << " /";
cout.width(5); cout << buscaAleatoria << "\n";
}
return 0;
}Saída obtida:
n | ordem crescente: altura / busca do ultimo | ordem aleatoria: altura / busca do ultimo
500 | 500 / 500 | 21 / 10
1000 | 1000 / 1000 | 20 / 15
2000 | 2000 / 2000 | 25 / 17
4000 | 4000 / 4000 | 29 / 16As mesmas 4000 chaves produziram árvores completamente diferentes:
- Inserção em ordem crescente: cada chave nova é maior que todas e vai para a direita da anterior. A altura é n, e a busca pelo último elemento faz 4000 comparações, pior caso O(n).
- Inserção em ordem aleatória: a altura ficou entre 20 e 29, na ordem de grandeza de log₂ n (≈ 12 para n = 4000), e as buscas fizeram em torno de 10 a 17 comparações.
Isso explica por que existem as árvores balanceadas (AVL, rubro-negras): elas reorganizam a árvore a cada inserção para manter h = O(log n) mesmo com entradas ordenadas, transformando a garantia de “caso médio” em garantia de pior caso. Em C++, std::set e std::map oferecem busca, inserção e remoção em O(log n), e costumam ser implementados com árvores desse tipo.
Escolhendo com base na complexidade
Com esses resultados, decisões de projeto ficam argumentáveis:
- Precisa de muitas buscas em dados que quase não mudam? Ordene uma vez (O(n log n)) e use busca binária (O(log n) por consulta).
- Precisa inserir e remover o tempo todo, sempre pelas pontas? Pilha ou fila bem implementadas (O(1)).
- Precisa de acesso por posição?
vector. Precisa inserir no meio ou no início com frequência? Considere lista encadeada, mas lembre-se do custo de chegar até a posição. - Os dados chegam em ordem previsível e você usa árvore de busca? Prefira uma árvore balanceada.
Limitações da análise
- Constantes importam para n pequeno. Um algoritmo O(n²) simples pode ser mais rápido que um O(n log n) sofisticado quando n é pequeno. Por isso implementações reais de ordenação costumam usar métodos simples em trechos pequenos.
- Pior caso nem sempre é o caso típico. Um algoritmo pode ter pior caso ruim e comportamento médio excelente, e vice-versa.
- Memória também é recurso. A versão B usa O(n) de memória extra e a C também; a A usa O(1). Há uma troca (trade-off) entre tempo e espaço.
- O modelo é uma abstração. Ao contar “comparações”, ignoramos cache, alocação de memória e outros custos de hardware, que o experimento com
chronorevelou na versão C. - Medição de tempo é ruidosa. Os tempos acima vêm de uma única execução por tamanho. Medições rigorosas repetem o experimento várias vezes e usam mediana ou média.
- A tabela é um resumo. Ela apresenta custos usuais; implementações concretas (e o hardware) podem alterar constantes e detalhes, como o espaço desperdiçado pela fila com índice ou a localidade de memória da lista encadeada, que costuma ser pior que a do
vector. - Este artigo não cobre a demonstração formal da análise amortizada, notações o e ω, nem a resolução geral de recorrências (como o Teorema Mestre), assuntos para um estudo posterior.
Síntese
Resumindo o percurso com o nosso problema das matrículas duplicadas (a síntese das estruturas clássicas está na tabela de referência da seção anterior):
| Versão | Ideia | Tempo (pior caso) | Memória extra |
|---|---|---|---|
| A | comparar todos os pares | Θ(n²) | O(1) |
| B | ordenar e olhar vizinhos | O(n log n) | O(n) |
| C | conjunto de dispersão | O(n) em média | O(n) |
A teoria permitiu prever o comportamento (n(n−1)/2 comparações; fator 4 quando n dobra) e a prática o confirmou, ao mesmo tempo em que mostrou o limite da teoria: a classe assintótica diz como o custo cresce, não quem é mais rápido em um n específico. Boa engenharia combina as duas coisas: raciocinar sobre a complexidade para descartar soluções que não escalam e medir para decidir entre as que sobrevivem.
As estruturas de dados clássicas seguem a mesma lógica. Pilhas e filas bem implementadas dão operações O(1); vector e lista encadeada trocam acesso por posição por inserção no início; árvores de busca são O(log n) quando equilibradas e O(n) quando degeneram; e algoritmos de ordenação como inserção e intercalação diferem por um fator que, para n grande, chega a centenas de vezes. Conhecer o custo de cada operação é o que permite escolher a estrutura certa para cada problema.
Referências
INTERNATIONAL ORGANIZATION FOR STANDARDIZATION; INTERNATIONAL ELECTROTECHNICAL COMMISSION. ISO/IEC 14882:2017: Programming languages — C++. 5. ed. Genebra: ISO/IEC, 2017.
CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN, Clifford. Introduction to algorithms. 4. ed. Cambridge, MA: MIT Press, 2022.
KNUTH, Donald E. Big omicron and big omega and big theta. ACM SIGACT News, New York, v. 8, n. 2, p. 18-24, 1976.
SEDGEWICK, Robert; WAYNE, Kevin. Algorithms. 4. ed. Upper Saddle River: Addison-Wesley, 2011.
Atividade de fixação
- Análise. Classifique cada trecho em O(1), O(n), O(n²) ou outra classe, justificando:
- (a) um laço
for (int i = 0; i < n; i++)que somav[i]; - (b) dois laços aninhados, cada um de 0 a n, com corpo constante;
- (c) um laço
while (n > 1) { n = n / 2; }.
- (a) um laço
- Demonstração. Mostre, encontrando c e n₀, que 4n² + 10n = O(n²).
- Experimento. Altere
contagem.cpppara que a lista tenha uma matrícula duplicada logo nas duas primeiras posições. Quais contagens mudam, e por quê? Isso é melhor caso ou pior caso? - Estruturas. Usando a tabela de referência, indique a estrutura mais adequada e justifique em termos de complexidade: (a) histórico de “desfazer” de um editor de texto; (b) fila de impressão; (c) cadastro com milhões de matrículas consultado muito mais vezes do que alterado.
- Experimento com árvores. Em
arvore.cpp, insira as chaves em ordem decrescente. Qual será a altura? Depois, insira primeiro a chave do meio, depois as metades de forma recursiva, e observe o que acontece com a altura. - Ordenação. Em
ordenacao.cpp, crie uma lista “quase ordenada” (ordenada, com apenas 10 pares de elementos trocados) e conte as comparações da inserção. Qual caso ela se aproxima? Isso muda sua escolha de algoritmo? - Reflexão. Na medição de tempo, a versão C (O(n) em média) foi mais lenta que a B (O(n log n)). Em que situação você apostaria que a C passaria a ganhar? Como testaria sua hipótese?