Cheat sheet

n conta elementos, h mede altura em arestas, V,E contam vértices e arestas. Custos de comparação e hash são constantes só com chaves de dimensão limitada. Consulta aqui a condição; a demonstração está no capítulo ligado.

Prova e contagem

Precisas de	Usa
Contrato	Pré do chamador e pós do algoritmo, com empates e vazio
Ciclo	Início, manutenção, implicação à saída e medida que diminui
Recursão	Caso base e hipótese nos menores

$O$ limita por cima, $\Omega$ por baixo, $\Theta$ pede os dois. Média exige distribuição. Amortizado limita sequências sem sorteio.

Padrão	Custo
Um percurso	$\Theta(n)$
n interiores por cada exterior	$\Theta(n^2)$
1+…+n	$\Theta(n^2)$
Duplicar de i=1 enquanto i<n, n>=1	$\lceil\log_2 n\rceil$ iterações
Duplicar com interior proporcional a i	$\Theta(n)$
Metade com junção linear	$\Theta(n\log n)$
Prefixos e q somas	$\Theta(n+q)$ com $p[r]-p[l]$
Janela k em N	$\Theta(N)$ com retira a[i-1] e junta a[i+k-1]

Provas e recorrências.

Pesquisa e ordenação

Binária em vetor ordenado: $O(\log(n+1))$. Em [l,r), m=l+(r-l)/2. Linear sem ordem: $\Theta(n)$.

Limite	Primeiro	Descarta esquerda com
Lower	>=x	v[m]<x
Upper	>x	v[m]<=x

Contagem de x: upper menos lower. Podem devolver n. Resposta monótona inclui o custo do teste.

Ordenação	Pior	Extra	Empates
Seleção	$\Theta(n^2)$	$O(1)$	Não
Inserção	$\Theta(n^2)$	$O(1)$	Sim
Merge	$\Theta(n\log n)$	$O(n)$	Sim, esquerda primeiro
Quicksort	$\Theta(n^2)$	Pilha até $O(n)$	Não
Heapsort	$O(n\log n)$	$O(1)$	Não
Counting	$\Theta(n+k)$	$O(n+k)$	Sim, da direita

Comparar tem limite $\Omega(n\log n)$. sort pede ordem fraca estrita e não é estável. Radix exige passagem estável. Limites e traços.

Estruturas e geometria

Operação	Vetor	Lista simples
Consultar índice i	$O(1)$	$O(n)$
Inserir na frente	$O(n)$ por deslocação	$O(1)$
Consultar o fim	$O(1)$	$O(1)$ com cauda, $O(n)$ sem ela
Inserir no fim	$O(1)$ amortizado	$O(1)$ com cauda
Remover no fim	$O(1)$	$O(n)$ sem anterior na simples
Inserir depois de nó conhecido	Desloca os seguintes	$O(1)$
Remover nó conhecido	Desloca os seguintes	$O(n)$ sem anterior na simples

Pilha é LIFO, fila é FIFO, deque aceita ambas as pontas. Duas pilhas fazem fila se transferirem só com saída vazia. TADs e ligações.

Orientação: $(q_x-p_x)(r_y-p_y)-(q_y-p_y)(r_x-p_x)$. Positivo vira à esquerda. Graham ordena em $O(n\log n)$ e varre em $O(n)$. Ponto em convexo com c vértices: $O(\log c)$. Envolvente.

Árvores

Vazio tem altura -1 e folha tem altura 0. Para um nó com alturas h_e e h_d nas subárvores, $h=1+\max(h_e,h_d)$. Pré visita raiz, esquerda e direita; em visita esquerda, raiz e direita; pós visita esquerda, direita e raiz. Cada percurso custa $\Theta(n)$. Binárias.

BST exige ordem global, não só pai-filho. Operações $O(h+1)$, pior $O(n)$. Dois filhos troca com sucessor. BST.

AVL	Repara com
LL	Direita
RR	Esquerda
LR	Esquerda no filho, direita no nó
RL	Direita no filho, esquerda no nó

Vermelha-preta: raiz e NIL pretos, sem vermelhos seguidos, mesma altura preta. Altura até $2\log_2(n+1)$. Equilíbrio.

Hash, heaps e grafos

Procuras em hash	Condição
Provar desigualdade	Hash diferente prova; hash igual não prova igualdade
Custo do encadeamento	$O(1+\alpha)$ em média, $\alpha=n/m$, sob dispersão uniforme e custos constantes
Remover em aberto	Marca apagada: a pesquisa atravessa, a inserção memoriza e continua até excluir duplicado
Passo duplo válido	Coprimo com m; com m primo, qualquer $1\le passo<m$

Dispersão.

Com n>0 elementos em vetor zero-based, os filhos de i são 2i+1,2i+2 e o pai de i>0 é $\lfloor(i-1)/2\rfloor$ com divisão inteira. Topo $O(1)$ com heap não vazio, alteração $O(\log n)$, construção $\Theta(n)$. Heaps.

Listas $O(V+E)$, matriz $O(V^2)$. BFS usa fila e dá o menor número de arestas, só em grafos sem pesos. DFS usa pilha.

Procuras	Condição	Ação
Ciclo dirigido	Aresta para vértice cinzento	Segue os pais até ao antepassado
Ordem válida	DAG confirmado: Kahn retira os V vértices	Usa a ordem de saída; incompleta não serve
Componente fechada	low[u]==disc[u] em Tarjan	Retira da pilha até u
Ponte numa aresta u->v da árvore DFS, grafo não dirigido	low[v]>disc[u]	Marca u-v; paralelas anulam

Grafos e aplicações.