Complexidade e estruturas

Procurar um valor num vetor desordenado de $n$ elementos pode exigir $n$ comparações no pior caso. Se o mesmo vetor estiver ordenado, a pesquisa binária compara com o elemento do meio e descarta metade dos candidatos em cada passo, com $O(\log n)$ comparações. A ordenação prévia torna possível essa escolha, mas tem um custo próprio que a análise deve incluir quando ainda está por fazer.

Para comparar algoritmos sem depender da máquina, identifica três elementos antes de anunciar um custo: o tamanho da entrada, as operações contadas e a estrutura que as suporta. Uma escolha matematicamente correta pode ficar lenta se a implementação repetir procuras ou copiar dados em cada passo.

O que é o tamanho da entrada

Num vetor, $n$ costuma ser o número de elementos. Num grafo, escreve $n=|V|$ para os vértices e $m=|E|$ para as arestas. Uma lista de adjacência ocupa $\Theta(n+m)$ espaço. Dizer apenas que um algoritmo de grafos é linear esconde a representação, por isso indica sempre se o custo é em $n$, em $m$ ou nos dois.

Numa mochila, $W$ é uma capacidade numérica e não o número de bits da entrada. O inteiro $W$ precisa de $\Theta(\log(W+1))$ bits para ser escrito. Uma tabela com $W+1$ colunas pode ser enorme mesmo quando escrever $W$ ocupa poucos caracteres. Esta diferença entre valor e representação explica o custo pseudopolinomial da programação dinâmica: a tabela cresce com o valor, não com o tamanho da sua escrita.

A análise habitual conta operações elementares de custo constante. Quando os números podem crescer sem limite, somar ou multiplicar inteiros passa a depender do número de bits. Nos exemplos de C++ desta cadeira, assume valores que cabem nos tipos usados e respeita os limites indicados em cada enunciado.

O, Ω e Θ

Para funções não negativas, $f\in O(g)$ significa que existem $c>0$ e $n_0$ tais que $f(n)\le cg(n)$ para todo $n\ge n_0$. É um limite superior. $f\in\Omega(g)$ troca essa desigualdade por $f(n)\ge cg(n)$ e dá um limite inferior. $f\in\Theta(g)$ exige os dois.

Por exemplo, $f(n)=3n^2+10n+5$. Para $n\ge1$, temos $3n^2\le f(n)\le18n^2$, logo $f\in\Theta(n^2)$. Também é verdade que $f\in O(n^3)$, mas esse limite informa menos. Dizer $O(n^2)$ não afirma que toda a entrada demora exatamente esse tempo, nem que o melhor caso é quadrático.

A ordem dos crescimentos mais usados é

$$1\prec\log n\prec n\prec n\log n\prec n^2\prec n^3\prec 2^n\prec n!.$$

A base do logaritmo altera uma constante. Uma potência $n^k$ com $k$ fixo é polinomial. Em $2^n$, acrescentar um elemento duplica o número de candidatos; em $n!$, a multiplicação depende de $n$.

Contar ciclos

Estes dois ciclos não fazem o mesmo trabalho:

// Excertos: n é positivo e cada operação do corpo custa O(1).
for (int i = 0; i < n; ++i)
    for (int j = 0; j < i; ++j)
        operacao();

for (int i = 1; i < n; i *= 2)
    operacao();

O primeiro faz $0+1+\cdots+(n-1)=n(n-1)/2$ operações, portanto $\Theta(n^2)$. O segundo visita $1,2,4,\ldots$ e termina ao atingir $n$, portanto faz $\Theta(\log n)$ operações. O código real deve evitar overflow de i; aqui o excerto descreve apenas a contagem.

Uma sequência de dois passos soma os custos. Um ciclo soma o custo de cada iteração. Multiplicar dois limites só é correto quando esse produto corresponde ao número de vezes que o trabalho interno ocorre. Se uma BFS percorre a lista de cada vértice uma vez, o total dessas listas é $m$, não $nm$.

Melhor caso, pior caso e custo amortizado

Na procura linear, um alvo na primeira posição exige uma comparação; um alvo ausente exige $n$. Temos melhor caso $\Theta(1)$ e pior caso $\Theta(n)$. O caso médio exige uma distribuição de entradas. Não podemos obtê-lo apenas pela média desses dois limites.

Uma inserção no fim de vector é amortizadamente $O(1)$. Algumas inserções provocam realocação e copiam $\Theta(n)$ elementos, mas uma sequência de $n$ inserções tem custo total $O(n)$ com crescimento geométrico da capacidade. Amortizado é uma garantia sobre sequências de operações; médio é uma expectativa sobre uma distribuição.

Estruturas e operações

Estrutura	Operações úteis	Custo e condição
Vetor	Acesso por índice	$\Theta(1)$
Vetor ordenado	Pesquisa binária	$O(\log n)$; manter a ordem pode exigir deslocar $O(n)$ elementos
Fila/pilha	Inserir e retirar na extremidade adequada	$O(1)$ nas implementações habituais
Heap binário	Inserir, extrair mínimo	$O(\log n)$; consultar mínimo é $O(1)$
Árvore de pesquisa equilibrada	Procurar, inserir, remover	$O(\log n)$
Tabela de dispersão	Procurar e inserir	$O(1)$ esperado com dispersão e ocupação adequadas; pior caso $O(n)$
Union-find	Unir componentes, encontrar representante	$O(\alpha(n))$ amortizado com compressão de caminhos e união por rank/tamanho

A fila de prioridade da STL não tem decreaseKey. Em Dijkstra podemos inserir um novo par (distância, vértice) e ignorar os pares antigos quando saem. Essa decisão muda a contagem de entradas da heap. Não alteres um campo usado pelo comparador de um objeto já na heap e esperes que ela se reorganize sozinha.

Representar grafos

Uma matriz de adjacência usa $\Theta(n^2)$ espaço e testa se existe uma aresta em $\Theta(1)$. Percorrer todos os vizinhos de um vértice custa $\Theta(n)$, mesmo que tenha poucas arestas.

Uma lista usa $\Theta(n+m)$ espaço e percorre os vizinhos em $\Theta(\deg(u))$. Num grafo não dirigido guardamos normalmente cada aresta nos dois sentidos, o que multiplica o espaço por dois e mantém a mesma ordem assimptótica. Arestas paralelas e pesos zero devem ter uma representação explícita; zero não deve significar simultaneamente “não há aresta” e “há uma aresta de custo zero”.

Um grafo esparso pode ter $m=O(n)$; um grafo simples denso pode ter $m=\Theta(n^2)$. Assim, $O((n+m)\log n)$ e $O(n^2)$ são alternativas diferentes conforme a densidade. A escolha vem das operações necessárias e dos limites da entrada.

Compor subrotinas sem esconder o crescimento

Quando um algoritmo chama outro, o tamanho da entrada da chamada interna pode depender da entrada original. Se uma fase produz uma lista de tamanho $\Theta(n^2)$ e a fase seguinte a ordena, o custo total inclui $\Theta(n^2\log n)$, não apenas o custo da segunda fase no seu próprio parâmetro. Substitui o tamanho efetivo antes de somar.

Operações aritméticas também dependem da representação. Somar números de $k$ bits custa $\Theta(k)$; multiplicar pode custar mais conforme o algoritmo usado. Nos limites de DA, cada operação sobre índices e pesos cabe nos tipos indicados e conta $O(1)$. Quando a capacidade $W$ ou o alvo $T$ fazem parte da entrada binária, o número de bits $\Theta(\log W)$ é o tamanho relevante, e uma tabela com $W$ colunas é exponencial nesse tamanho.

O que entregar numa análise

Para uma solução, identifica os parâmetros, conta estados ou operações, inclui a estrutura de suporte e separa tempo de memória auxiliar. Por exemplo: “a BFS com listas inicializa $n$ marcas e examina $m$ arestas, pelo que usa $O(n+m)$ tempo e $O(n)$ memória auxiliar, além do grafo”.