Correção, invariantes e complexidade

Prova em quatro passos

• Contrato: pré-condição do chamador e pós-condição do algoritmo, com empates e vazio decididos.
• Invariante vale à entrada de cada iteração. Mostra início, manutenção e implicação à saída.
• Junta quantidade inteira não negativa que diminui para garantir paragem. Sem ela, tens correção parcial.

Primeira posição do máximo em vetor não vazio:

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

Invariante: melhor é a primeira posição do máximo em [0,i). Fecha com i=n. Usa > para conservar o primeiro; >= daria o último. São n-1 comparações.

Contar sem adivinhar

Padrão	Total	Ordem
Seguidos de n	2n	$\Theta(n)$
Encaixados de n, n interiores por exterior	$n^2$	$\Theta(n^2)$
1+…+n	$n(n+1)/2$	$\Theta(n^2)$
Duplicar de i=1 enquanto i<n, n>=1	$\lceil\log_2 n\rceil$ iterações	$\Theta(\log n)$
Duplicar com interior i	$<2n$	$\Theta(n)$

Ciclos seguidos somam os custos; ciclos encaixados com interior independente multiplicam as contagens, e o caso triangular soma 1+…+n. Copiar n posições custa $\Theta(n)$. Percorrer uma string de comprimento L custa $\Theta(L)$ por passagem; juntar com += repetido recopia o acumulado em cada passo, por isso fixa a operação antes de contar.

Limites e recorrências

• $O$ limita por cima, $\Omega$ por baixo, $\Theta$ pede os dois. Indica sempre o caso: $O$ não significa pior caso.
• $3n^2+7n+4$ cabe entre $3n^2$ e $14n^2$ para $n\ge1$: $\Theta(n^2)$.
• Ordem usual: $1\prec\log n\prec n\prec n\log n\prec n^2\prec2^n\prec n!$.

Recorrência	Resultado
$2T(n/2)+\Theta(n)$	$\Theta(n\log n)$
$2T(n/2)+\Theta(1)$	$\Theta(n)$
$T(n/2)+\Theta(1)$	$\Theta(\log n)$
$T(n-1)+\Theta(n)$	$\Theta(n^2)$

Pilha recursiva ocupa $O(h)$. Média exige distribuição; amortizado limita sequências sem sorteio. Vetor que duplica dá $O(1)$ amortizado por inserção.

Somas rápidas

Prefixos $p[0]=0$, $p[i+1]=p[i]+v[i]$ dão soma de [l,r) como $p[r]-p[l]$. Construção $\Theta(n)$, consulta $\Theta(1)$.

1. Vetor
   4-271
   [1,3) soma -2 e 7.
2. Prefixos
   042910
   5 vem de 9 menos 4.

• Janela fixa K: desliza a soma em $\Theta(N)$. «Metade ou mais» testa 2*dentro>=K.
• Kadane para intervalo não vazio: atual=max(x,atual+x), melhor=max(melhor,atual). Tempo $O(n)$. Só negativos devolvem o maior elemento.

Provas completas.