Correção, invariantes e complexidade

Em [6,9,9,2], a nota máxima é 9, mas há duas posições possíveis. Se o pedido for a primeira ocorrência, a resposta é 1, com índices a partir de zero. Um algoritmo tem de fixar estes empates antes de podermos provar que está correto. Ordenar todas as notas para descobrir um único máximo faz trabalho que um percurso evita.

Percorrer o vetor guardando a maior nota vista é um algoritmo: uma sequência finita de passos para transformar a entrada no resultado pedido. Além de justificar esse resultado, precisamos de contar tempo e memória.

Contrato e invariante

O contrato separa a pré-condição, que o chamador garante, da pós-condição, que o algoritmo garante. Para procurar o máximo, o vetor tem pelo menos um elemento. A resposta é um valor presente no vetor e nenhum elemento é maior. Se também pedires a posição, tens de decidir o que acontece num empate.

Considera este pseudocódigo, que devolve a primeira posição do máximo num vetor não vazio:

melhor = 0
para i = 1, ..., n-1:
    se v[i] > v[melhor]: melhor = i
devolver melhor

1. Inicialização: antes da primeira iteração, i=1. O prefixo só contém v[0]. melhor=0 satisfaz a propriedade.
2. Manutenção: se v[i] for maior, a posição i passa a ser o novo máximo. Se for menor ou igual, manter a posição antiga conserva o máximo e o primeiro empate. Depois de aumentar i, a propriedade vale para o prefixo seguinte.
3. Conclusão: ao sair, i=n. O prefixo é o vetor inteiro. A propriedade implica a pós-condição.
4. Terminação: a quantidade inteira não negativa n-i diminui em cada passo. O ciclo não pode continuar indefinidamente.

As três primeiras etapas dão correção parcial: se terminar, o resultado é correto. Com a terminação, tens correção total. Uma propriedade como «o máximo ainda existe» é demasiado fraca para justificar a posição devolvida. Usar >= conserva o máximo, mas passa a escolher a última ocorrência.

Contar operações

Escolhe uma operação representativa, como comparações de chaves, e conta-a em função do tamanho n. O máximo anterior faz exatamente n-1 comparações. Não precisa de ordenar, porque isso acrescentaria trabalho sem melhorar uma única consulta. A tabela seguinte distingue os dois casos que mais se confundem: ciclos seguidos somam, e ciclos encaixados com interior independente multiplicam; o caso triangular soma 1+…+n.

No primeiro programa, o segundo ciclo começa depois de terminar o primeiro. No segundo, o ciclo interior executa n vezes em cada iteração exterior, independentemente de i. Por isso somamos custos no primeiro e multiplicamos contagens no segundo; quando o interior depende do exterior, conta por soma, como no caso triangular.

long long s = 0;
for (int i = 0; i < n; ++i) s += a[i];
for (int i = 0; i < n; ++i) s += b[i]; // total 2n passos

long long s = 0;
for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j) s += 1; // total n*n passos

Com n=0, ambos fazem zero iterações. Com n=1000, o primeiro faz cerca de 2000 adições e o segundo cerca de 1 000 000. Chamar «independentes» aos dois casos esconde esta diferença: o que importa é se um ciclo está dentro do outro. E não classifiques todos os ciclos encaixados como quadráticos: se o exterior duplica i e o interior executa i vezes, a soma é $1+2+4+\cdots<2n$, ou seja, $\Theta(n)$. Um índice que apenas avança ao longo de todo o programa pode justificar uma soma linear, mesmo dentro de outro ciclo.

O modelo costuma tratar operações sobre inteiros de dimensão fixa e acesso a uma posição de array como constantes. Comparar duas strings com comprimento máximo L pode custar $O(L)$. Copiar um vetor de n posições custa $\Theta(n)$, mesmo que a chamada pareça uma única instrução. Juntar strings com += repetido recopia o resultado parcial em cada passo, por isso n junções podem custar $\Theta(n^2)$ no total: conta a operação repetida, não só o comprimento final.

Limites assintóticos

Para funções não negativas a partir de certa dimensão:

• $T(n)\in O(f(n))$ se existem $c>0,n_0$ com $T(n)\le c f(n)$ para todo $n\ge n_0$.
• $T(n)\in\Omega(f(n))$ se existe um limite inferior análogo.
• $T(n)\in\Theta(f(n))$ se os dois limites valem.

Para $T(n)=3n^2+7n+4$, com $n\ge1$, temos $3n^2\le T(n)\le14n^2$. Logo $T(n)\in\Theta(n^2)$. Também pertence a $O(n^3)$, mas esse limite informa menos. E $O$ não significa «pior caso»: podes dar um limite superior para o melhor caso, o caso médio ou o pior caso, desde que indiques qual analisaste.

Se pedirem a relação mais apertada entre duas funções, tenta primeiro $\Theta$. Por exemplo, $6n^2+5\in\Theta(n^2)$: para $n\ge1$, basta escolher constantes 6 e 11, pois $6n^2\le6n^2+5\le11n^2$. O facto de a função exceder $n^2$ não refuta $O(n^2)$; o limite permite uma constante multiplicativa.

Já $n\log_2n\in O(n^2)$, mas não em $\Theta(n^2)$. O quociente $\log_2n/n$ tende a zero. Para qualquer constante positiva c que proposes como limite inferior, esse quociente acaba por ficar abaixo de c. Portanto não existe um limite inferior quadrático que valha para todas as dimensões suficientemente grandes. Um limite superior isolado não prova uma ordem apertada.

A notação $\sum$ indica uma soma dos termos nos limites escritos. Por exemplo, $\sum_{i=1}^{n}i=1+2+\cdots+n$. $\log_2 n$ é o expoente que dá n como potência de 2; conta aproximadamente quantas divisões por dois reduzem n até um. $n!$ é o produto $1\cdot2\cdots n$.

A ordem de crescimento habitual é

A base do logaritmo muda apenas uma constante. Uma medição de 0,4 s com dimensão n sugere cerca de 1,6 s ao duplicar n num algoritmo quadrático, se a parcela quadrática dominar e as condições forem semelhantes. É uma estimativa, não uma garantia sobre outra máquina ou outra distribuição de dados.

O vídeo de Rodrigo Dias complementa o estudo de invariantes e análise assintótica.

Invariantes e Análise Assintótica 101Carregar vídeo do YouTube

Abrir no YouTube

Recorrências e espaço

Uma função recursiva chama-se a si própria para resolver um problema menor. O caso base resolve diretamente um problema pequeno, sem nova chamada. Para provares terminação, verifica que cada chamada reduz uma dimensão inteira não negativa até ao caso base. A hipótese indutiva assume a correção dos subproblemas menores; tens de explicar como os seus resultados resolvem o problema atual. Cada chamada suspensa conserva parâmetros e variáveis na pilha de chamadas.

Uma recorrência exprime o custo de uma chamada pelo trabalho local e pelo custo das chamadas menores. Assume custo constante no caso base; divisões em metades de dimensão ímpar usam arredondamentos, que não alteram as ordens seguintes.

Uma chamada que resolve duas metades e faz trabalho linear satisfaz $T(n)=2T(n/2)+\Theta(n)$. Em cada nível da árvore de chamadas, o trabalho total é $\Theta(n)$ e há $\Theta(\log n)$ níveis. O total é $\Theta(n\log n)$.

Calcular o máximo de duas metades e comparar os dois resultados faz trabalho constante por chamada: $T(n)=2T(n/2)+\Theta(1)$. Os níveis têm 1, 2, 4, … chamadas e a soma até às n folhas é $2n-1$, ou seja, $\Theta(n)$. Ter duas chamadas recursivas não implica custo $n\log n$, porque o custo da junção é decisivo.

Uma chamada que só segue uma metade com trabalho constante satisfaz $T(n)=T(n/2)+\Theta(1)=\Theta(\log n)$. Uma chamada que reduz o tamanho em um e percorre o restante satisfaz $T(n)=T(n-1)+\Theta(n)=\Theta(n^2)$.

Conta também o espaço auxiliar, sem a entrada e a saída quando essa convenção é explícita. Uma recursão com profundidade h ocupa $O(h)$ na pilha de chamadas. Duas chamadas consecutivas não exigem o espaço das duas subárvores ao mesmo tempo. Um vetor auxiliar reutilizado de tamanho n mais uma pilha de profundidade $\log n$ custa $O(n)$.

Pior caso, média e amortização

O pior caso maximiza o custo entre entradas da mesma dimensão. O caso médio exige uma distribuição de probabilidades: não basta dizer «normalmente». Com chaves distintas, um quicksort com pivô uniforme tem custo esperado $O(n\log n)$ devido à escolha aleatória do pivô, embora ainda exista uma execução quadrática. A partição também importa: Lomuto com chaves todas iguais continua quadrático, mesmo com pivô aleatório.

A análise amortizada limita uma sequência de operações, sem assumir entradas aleatórias. Num vetor que duplica a capacidade quando fica cheio, as cópias ao inserir n elementos somam $1+2+4+\cdots<2n$. Uma inserção isolada pode custar $\Theta(n)$, mas o custo amortizado por inserção é $O(1)$. Realocar pode invalidar referências e iteradores, mesmo com custo amortizado baixo.

Pré-processar consultas

Para responderes à soma de um intervalo [l,r), constrói prefixos: $p[0]=0$ e $p[i+1]=p[i]+v[i]$. Por indução, $p[i]$ é a soma das primeiras i posições. Assim,

Construir custa $\Theta(n)$, cada consulta custa $\Theta(1)$, e q consultas custam $\Theta(n+q)$ no total. Somar cada intervalo de novo pode custar $\Theta(nq)$. Se o vetor mudar, os prefixos deixam de corresponder aos dados.

#include <iostream>
#include <vector>
int main() {
    int n, q;
    if (!(std::cin >> n >> q) || n < 0 || n > 10000 || q < 0) return 1;
    std::vector<long long> p(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        int x;
        if (!(std::cin >> x) || x < -1000000 || x > 1000000) return 1;
        p[i + 1] = p[i] + x;
    }
    for (int i = 0; i < q; ++i) {
        int l, r;
        if (!(std::cin >> l >> r) || l < 0 || r < l || r > n) return 1;
        std::cout << p[r] - p[l] << '\n';
    }
}

Na entrada inicial, v=[4,-2,7,1] dá p=[0,4,2,9,10]. A consulta [1,3) retira o prefixo de soma 4 ao prefixo de soma 9: ficam -2+7=5. [2,2) dá zero e [0,4) dá 10. O programa aceita o intervalo vazio e limita os valores para que a soma caiba em long long. Testa também n=0, q=1 e a consulta 0 0.

Janela deslizante com contagem

Na ficha atual 02, o problema [AED008] Saving Pipefish pede o número de janelas de tamanho K com pelo menos metade das posições com valor maior ou igual a T (2026/27). Recontar cada janela do zero custa $O(NK)$. Mantém antes uma contagem da janela atual.

O invariante é: antes de avaliar a janela que começa em i, dentro conta quantas das K posições dessa janela satisfazem profundidade[j] >= T. Para passar de i para i+1, retira a posição i e acrescenta a posição i+K. Cada posição entra e sai uma vez, logo o total é $\Theta(N)$ após a primeira janela.

Com N=7, K=3, T=150 e [142,155,147,165,150,112,73], as contagens são 1,2,2,2,1 e há 3 janelas válidas. Com K=1, cada janela tem uma posição e a resposta conta os elementos >=T. Com K=N, há uma única janela. Verifica sempre 1<=K<=N antes de aceder a a[i+K].

int validas(const std::vector<int>& a, int k, int t) {
    int n = (int)a.size(), dentro = 0;
    for (int i = 0; i < k; ++i) if (a[i] >= t) ++dentro;
    int r = (dentro * 2 >= k);
    for (int i = 1; i + k <= n; ++i) {
        if (a[i - 1] >= t) --dentro;
        if (a[i + k - 1] >= t) ++dentro;
        if (dentro * 2 >= k) ++r;
    }
    return r;
}

Multiplicar por dois evita divisão inteira no teste «pelo menos metade», incluindo K ímpar.

Máximo de uma janela fixa

A maior soma de exatamente k elementos consecutivos é outro contrato. Com [4,-1,3,-2,5,-3] e k=3, as somas são 6,0,6,0; a primeira janela máxima começa em 0. Kadane permite comprimentos diferentes, pelo que não resolve este pedido sem alteração.

Assume 1<=k<=n e somas representáveis. Soma primeiro [0,k), iniciando c=s nessa soma e p=0. Começa j=1; enquanto j<=n-k, faz:

c = c - x[j - 1] + x[j + k - 1];
if (c > s) { s = c; p = j; }
++j;

No teste do ciclo, c é a soma da janela que começa em j-1; s é a maior soma entre as janelas com inícios em [0,j), e p é o primeiro desses inícios que atinge s. Dizer só que s é um máximo não explica por que a atualização de c calcula a janela seguinte.

Inicialmente, j=1 e só a janela de início 0 foi processada. Na manutenção, subtrair x[j-1] retira a posição antiga e somar x[j+k-1] acrescenta a nova. O teste estrito conserva o primeiro empate, e incrementar j volta a pôr c na janela de início j-1. Na saída, j=n-k+1, por isso foram consideradas todas as n-k+1 janelas. Essa quantidade menos j diminui até zero e prova terminação.

Recalcular cada janela custa $\Theta(k(n-k+1))$. Deslizar custa $\Theta(k+n-k)=\Theta(n)$, com espaço auxiliar $O(1)$. Com k fixo, as duas versões são lineares; com k=\lfloor n/2\rfloor, recalcular passa a quadrático e deslizar continua linear. Com k=n, existe uma única janela: até a versão que recalcula é linear. A hipótese k<=n/2, usada nalguns enunciados, permite simplificar o primeiro custo para $\Theta(nk)$; sem ela, mantém n-k+1.

Melhor soma contígua

Considera a maior soma de um intervalo não vazio. Enumerar todos os pares de extremos e somar cada intervalo custa $O(n^3)$. Atualizar a soma enquanto avanças o extremo direito reduz para $O(n^2)$; prefixos também avaliam cada par em tempo constante, mas deixam um número quadrático de pares.

Em [-3,5,-2,4,-8,6], os valores de atual são -3,5,3,7,-1,6, e a melhor soma é 7, do intervalo [5,-2,4]. Num vetor só de negativos, a resposta é o maior elemento, não zero. Se o intervalo vazio fosse permitido, zero passaria a ser uma resposta possível; seria outro contrato.

#include <algorithm>
#include <iostream>
#include <optional>
#include <vector>
std::optional<long long> melhorSoma(const std::vector<int>& a) {
    if (a.empty()) return std::nullopt;
    long long atual = a[0], melhor = a[0];
    for (std::size_t i = 1; i < a.size(); ++i) {
        atual = std::max<long long>(a[i], atual + a[i]);
        melhor = std::max(melhor, atual);
    }
    return melhor;
}
int main() {
    for (const std::vector<int>& a : {std::vector<int>{-3, 5, -2, 4, -8, 6},
                                     std::vector<int>{-6, -2, -8},
                                     std::vector<int>{}}) {
        const auto r = melhorSoma(a);
        if (r) std::cout << *r << '\n';
        else std::cout << "sem intervalo\n";
    }
}

O programa usa optional para representar a ausência de intervalo numa entrada vazia. Assume até 10 000 valores com módulo até um milhão para que as somas caibam em long long. Tempo $O(n)$ e espaço auxiliar $O(1)$. A saída negativa no segundo caso distingue este contrato de uma implementação que começa o melhor em zero.