CCM0128 - Computação II (2025i)

Seja \(A\) um conjunto de inteiros, que encontram-se armazenados em um vetor $a$. Seja $N$ a cardinalidade de $A$. Suponha que os elementos de $A$ ocorrem de forma estritamente crescente em $a$, isto é, $a[0]<a[1]<\dots<a[N-1]$. Neste exercício, definimos $A+A$ como sendo o conjunto $\{a[i]+a[j]:0\leq i<j<N\}$. Seja $x$ um inteiro. Queremos saber se $x$ ocorre em $A+A$. Na verdade, queremos saber quantos pares $(i, j)$ com $0\leq i<j<N$ são tais que $a[i] + a[j] = x$.

As funções countPlain() e count() em SumSearch.java abaixo determinam o número de pares $(i, j)$ como especificados acima. O algoritmo implementado em countPlain() é o algoritmo elementar, que tem complexidade de tempo $N^2$: se seu tempo de execução é $T_N$ para $A$ com $N$ elementos, então $T_N$ tem ordem de grandeza $N^2$.

(1) Prove que o algoritmo em count() tem complexidade de tempo não maior que $N$. Isto é, argumente que o tempo de execução $T_N$ de count() para vetores com $N$ elementos tem ordem de grandeza não maior que $N$. Note que, para tanto, basta você provar que o corpo do while em count() é executado não mais que, por exemplo, $N$ vezes.

(2) Prove que count() está correto, isto é, que ele determina corretamente o número de pares $(i, j)$ que queremos contar.

(3) Decida se o count() funciona corretamente no caso em que $a$ é apenas crescente, e não estritamente crescente. Isto é, decida se count() funciona se apenas sabemos que $a[0]\leq a[1]\leq\dots\leq a[N-1]$. Justifique sua resposta.

Sugestões. Para (1), considere a diferença $hi - lo$. Para (2), considere a afirmação

$A(lo, hi)$: O valor de $t$ é o número de pares $(i, j)$ com $i < j$ e $a[i] + a[j] = x$ satisfazendo a propriedade que ou $i < lo$ ou $j > hi$.

Considere os instantes $I_0,I_1,\dots$ em que o teste $lo<hi?$ do while em count() é executado. Note que $A(lo,hi)$ é verdade no instante $I_0$. Suponha agora que $A(lo,hi)$ vale no instante $I_{k-1}$. Argumente que $A(lo,hi)$ vale no instante $I_k$. Conclua (2) acima.