# Complexidade e invariantes

Notação assintótica para tempo e espaço, e invariantes para provar a correção de ciclos.

Página: https://resumos.rgo.pt/cadeiras/aed/complexidade-invariantes/

Dois programas fazem o mesmo e um deles demora o dobro. Qual escolhes? A resposta séria depende do tamanho da entrada: o dobro numa lista de dez elementos é ruído, numa lista de dez milhões é a diferença entre responder hoje e responder amanhã. A análise de complexidade mede como o custo cresce com a entrada, e os invariantes provam que o programa calcula o que promete. São as duas ferramentas que vais usar em todas as páginas desta cadeira.

## O que conta como custo

Fixar primeiro o que se mede: o **tamanho da entrada** $n$ (número de elementos, de vértices, de bits) e o **custo** que interessa (comparações, acessos à memória, operações elementares). O resto é ruído de máquina e ignora-se. Quando dissermos que um algoritmo é $O(n^2)$, estamos a dizer que o número de operações elementares cresce no máximo com o quadrado de $n$, a menos de constantes.

A notação Big-O descreve um **limite superior**: $f(n) = O(g(n))$ significa que, a partir de certo $n$, $f(n)$ fica abaixo de uma constante vezes $g(n)$. Há mais duas que vais encontrar: $\Omega$ para limite inferior (o algoritmo custa pelo menos isto) e $\Theta$ quando os dois limites coincidem (o custo é exatamente desta ordem). Na prática da cadeira, $O$ domina: queres garantir que o programa aguenta o pior caso.

Os tempos que interessam, do melhor para o pior: $O(1)$ constante, $O(\log n)$ logarítmico, $O(n)$ linear, $O(n \log n)$, $O(n^2)$ quadrático e $O(2^n)$ exponencial. Decora a intuição, não a lista: logaritmo é “cortar o problema a metade em cada passo”, $n \log n$ é “cortar e depois juntar”, quadrático é “comparar tudo com tudo”.

![Gráfico das curvas O(1), O(log n), O(n), O(n log n) e O(n²) para n de 1 a 10. A curva quadrática sobe muito mais depressa que as outras.](https://resumos.rgo.pt/cadeiras/aed/complexidade-invariantes/figura-1.svg)

Repara como a quadrática se destaca das outras mesmo com $n$ pequeno: é por isso que um algoritmo $O(n^2)$ aguenta os testes pequenos do Mooshak e rebenta no limite de tempo dos grandes.

## Linear contra binária em $n = 1000$

Recorda a [pesquisa linear e binária](https://resumos.rgo.pt/cadeiras/fp/algoritmos-complexidade/): a linear percorre o vetor até encontrar, a binária exige o vetor ordenado e descarta metade a cada comparação. Conta comparações no pior caso com $n = 1000$.

Na linear, o pior caso é o elemento estar na última posição ou não existir: $1000$ comparações. Na binária, cada comparação elimina metade dos candidatos: depois de $k$ comparações restam $1000 / 2^k$ elementos, e o processo termina quando resta um, ou seja $2^k \geq 1000$. Como $2^9 = 512$ e $2^{10} = 1024$, bastam $k = 10$ comparações. Mil contra dez, e a diferença aumenta com $n$: para um milhão, a linear faz um milhão de comparações e a binária faz $20$, porque $2^{20} = 1\,048\,576$.

O preço da binária está fora da pesquisa: alguém teve de ordenar o vetor primeiro, e ordenar custa pelo menos $O(n \log n)$[1](https://resumos.rgo.pt/cadeiras/aed/complexidade-invariantes/#user-content-fn-limite). Se pesquisares uma vez num vetor desordenado, ordenar mais pesquisar sai mais caro que a linear. A análise decide consoante o uso, não em abstrato.

```cpp
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v(1000);
    for (int i = 0; i < 1000; i++) v[i] = i;
    int alvo = 2000, linear = 0, binaria = 0;
    for (int x : v) { linear++; if (x == alvo) break; }
    int lo = 0, hi = 999;
    while (lo <= hi) {
        binaria++;
        int meio = (lo + hi) / 2;
        if (v[meio] == alvo) break;
        if (v[meio] < alvo) lo = meio + 1; else hi = meio - 1;
    }
    cout << "linear: " << linear << "\nbinaria: " << binaria << "\n";
}
```

O programa imprime `linear: 1000` e `binaria: 10`: o alvo 2000 não existe no vetor, por isso a linear percorre tudo e a binária parte o intervalo dez vezes até o esvaziar. Muda o alvo para 499 e vê as duas contagens caírem.

## Espaço também conta

A **complexidade espacial** mede a memória extra além da entrada. A pesquisa binária iterativa usa $O(1)$ de espaço extra (algumas variáveis); a versão recursiva usa $O(\log n)$ pela pilha de chamadas. O mergesort, que vais seguir na próxima página, precisa de um vetor auxiliar de tamanho $n$: tempo $O(n \log n)$, espaço $O(n)$. O quicksort no próprio vetor usa $O(\log n)$ de pilha em média. Quando a memória é curta, esta coluna da tabela pesa tanto como a do tempo.

## Invariantes: provar o ciclo

Complexidade diz quanto custa; **correção** diz que o resultado está certo. Para ciclos, a técnica é o **invariante**: uma afirmação sobre as variáveis que é verdadeira antes de cada iteração e que, combinada com a condição de saída, implica o resultado.

Toma a soma dos primeiros $n$ inteiros:

```
int soma = 0;
for (int i = 1; i <= n; i++) {
    soma += i;
}
```

O invariante é: antes da iteração com valor $i$, vale $soma = (i-1) \cdot i / 2$. Verifica por indução sobre $i$, como aprendeste em [indução](https://resumos.rgo.pt/cadeiras/md/inducao-recorrencia/): para $i = 1$, $soma = 0$ e $(1-1) \cdot 1 / 2 = 0$. Se vale para $i$, a iteração soma $i$ e obtém $(i-1) \cdot i / 2 + i = (i^2 - i + 2i)/2 = i \cdot (i+1)/2$, que é exatamente o invariante para $i+1$. Quando o ciclo termina, $i = n+1$, e o invariante dá $soma = n \cdot (n+1)/2$, a fórmula fechada. O invariante transforma “o ciclo parece somar tudo” numa prova.

Como escrever um invariante

Descreve o que já está feito em função do contador: “antes da iteração $i$, as primeiras $i-1$ posições estão tratadas”. Depois confirma três pontos: vale antes da primeira iteração, cada iteração preserva-o, e com a condição de saída ele implica o resultado. Se algum falhar, ou o invariante está mal escrito ou o programa tem um erro.

## Ver também

[Vídeo: CS50x 2024, aula 3: algoritmos e análise de custo](https://www.youtube.com/watch?v=jZzyERW7h1A)

A miniatura vem do YouTube. O vídeo só carrega quando clicas. [Abrir no YouTube](https://www.youtube.com/watch?v=jZzyERW7h1A)

Para rever o argumento das comparações com outra voz, a aula 3 do CS50x constrói a pesquisa binária e a notação assintótica a partir do zero.

## Para levar para a próxima página

A análise de um algoritmo não é a mesma coisa que a classe de um problema: um algoritmo concreto corre em $O(n^2)$ enquanto o problema pode admitir solução melhor. A distinção entre “este programa custa isto” e “este problema exige pelo menos isto” reaparece em [complexidade](https://resumos.rgo.pt/cadeiras/tc/complexidade/), com as classes P e NP. Já a seguir, aplica estas contas à [pesquisa e ordenação](https://resumos.rgo.pt/cadeiras/aed/complexidade-invariantes/pesquisa-ordenacao/).

## Notas de rodapé

1.  O limite $\Omega(n \log n)$ vale para ordenações que só comparam pares de elementos: com $n!$ ordens possíveis e dois resultados por comparação, são precisas pelo menos $\log_2(n!) \approx n \log n$ comparações. Segues a conta completa na [página de ordenação](https://resumos.rgo.pt/cadeiras/aed/complexidade-invariantes/pesquisa-ordenacao/). [Voltar](https://resumos.rgo.pt/cadeiras/aed/complexidade-invariantes/#user-content-fnref-limite)