T05 Busca em A + A
Seja um conjunto de inteiros, armazenados em um vetor a[]. Seja $N$ a cardinalidade de $A$. Suponha que os elementos de $A$ ocorrem de forma crescente em a[]. O conjunto $A+A$ é o conjunto $\{a[i]+a[j]:0\leq i<N,\;0\leq 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 $\Theta(N^2)$.
(1) Prove que o algoritmo em count() tem complexidade $\Theta(N)$. Note que basta provar que o corpo do laço while é executado $\Theta(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 no caso em que a[] contém elementos repetidos. 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$.
Prove, por indução no número de iterações do while, que a afirmação $A(lo, hi)$ é um invariante do laço, isto é, que $A(lo, hi)$ vale no início de cada iteração do while. Conclua que, quando saímos do laço, o valor de $t$ é o valor que queremos.
Você pode ler um pouco sobre invariantes em, por exemplo,
https://inst.eecs.berkeley.edu/~cs170/fa14/tutorials/tutorial1.pdf
- 9 ottobre 2021, 13:52
- 9 ottobre 2021, 13:52