T07 Busca em A + A
Seja \(A\) um conjunto de inteiros, 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) Argumente 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) Argumento 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 soma $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.
O método de prova esboçado no parágrafo acima é conhecido como o método de invariantes. Você pode ler um pouco sobre invariantes em, por exemplo,
https://inst.eecs.berkeley.edu/~cs170/fa14/tutorials/tutorial1.pdf
Exercício interessante (não é necessário entregar). As ideias envolvidas neste exercício possibilitam o projeto de um algoritmo quadrático para o 3SUM. Encontre tal algoritmo.
- 29 de octubre de 2023, 17:49
- 29 de octubre de 2023, 17:49