CCM0128 - Computação II (2025i)

Considere o Problema 3SUM: dada uma sequência de números \((a_i)_{0\leq i<N}\), determinar o número de triplas $(i, j, k)$ com $i<j<k$ e $a_i+a_j+a_k=0$. Um algoritmo elementar para resolver 3SUM é implementado no programa ThreeSum.java que vimos (também dado abaixo). Esse algoritmo tem complexidade de tempo $\Theta(N^3)$.

Observação. Estudamos a noção de ordem de crescimento de funções e a relevância desse conceito quando discutimos tempos de execução. Uma notação muito comum relacionada é a assim chamada notação assintótica, ou notação $O$, $\Omega$, e $\Theta$. Sejam $f(n)$ e $g(n)$ funções de $n$. Definimos a noção de (a) $f$ ser assintótico a $g$ (o que denotamos por $f\sim g$) e (b) $f$ ter ordem de crescimento $g$ (isto é, $f\sim cg$ para alguma constante $c>0$). Muitas vezes, queremos dizer que $f$ tem ordem de crescimento não maior que $g$: isto é, existem constantes $c>0$ e $n_0$ tais que $|f(n)|\leq cg(n)$ para todo $n\geq n_0$. Tal fato é denotado por $f=O(g)$. Também é conveniente poder expressar a noção que $f$ tem ordem de crescimento pelo menos $g$: isto é, existem constantes $c>0$ e $n_0$ tais que $|f(n)|\geq cg(n)$ para todo $n\geq n_0$. Tal fato é denotado por $f=\Omega(g)$. Quando $f=O(g)$ e $f=\Omega(g)$, escrevemos $f=\Theta(g)$. Leia mais sobre notação assintótica nesta página de P. Feofiloff.

Vimos como resolver 3SUM de forma consideravelmente mais eficiente, usando busca binária. É fácil ver que o algoritmo resultante tem complexidade de pior caso $O(N^2\log N)$ (isto é, para qualquer entrada com $N$ elementos, o tempo de execução é $O(N^2\log N)$). Também não é muito difícil ver que sua complexidade de pior caso é $\Omega(N^2\log N)$ (isto é, existe uma entrada com $N$ elementos para a qual o tempo de execução é $\Omega(N^2\log N)$). Assim, o programa ThreeSumBinary.java, que implementa esse algoritmo, tem complexidade de pior caso $\Theta(N^2\log N)$.

Comentamos em sala que existe um algoritmo de complexidade de tempo $\Theta(N^2)$ para 3SUM. Neste exercício, você implementará tal algoritmo. Seu programa deve chamar-se ThreeSumQuad.java. O main de seu programa ThreeSumQuad.java deve ser igual ao main de ThreeSum.java e ThreeSumBinary.java. Você deve implementar seu algoritmo quadrático na função count de seu programa ThreeSumQuad.java.

O algoritmo quadrático.  Para conceber o algoritmo quadrático para 3SUM, lembre-se do Exercício S01 Busca em A + A. Com aquele exercício em mente, será fácil desenvolver um algoritmo quadrático para 3SUM.

Elementos repetidos.  É necessário que valha uma hipótese importante para o funcionamento correto de ThreeSumBinary.java: a entrada de ThreeSumBinary.java não deve conter elementos repetidos; com entradas com repetição, ThreeSumBinary.java pode ter saída incorreta (por quê?).

Importante.  Seu programa quadrático ThreeSumQuad.java deve funcionar corretamente mesmo que haja repetições na entrada.

Integer overflow.  Tanto no programa ThreeSum.java como em ThreeSumBinary.java, não nos preocupamos com integer overflow. Da mesma forma, você não precisa se preocupar com integer overflow em seu programa ThreeSumQuad.java.

Gerador de entradas.  Para gerar entradas com as quais experimentar seu programa ThreeSumQuad.java, você pode usar os programas RandomInts.java e RandomIntsPlain.java. O programa RandomInts.java gera sequências sem repetição, enquanto que RandomIntsPlain.java gera sequências sem restrição quanto a repetições.

$ java-introcs RandomInts 10 20 121
-17 -8 -4 5 7 8 9 11 12 17
$ java-introcs RandomIntsPlain 10 20 121
-8 17 7 9 17 -17 8 11 12 -4
$

Nos exemplos acima, $10$ indica que queremos $10$ inteiros e $20$ indica que queremos números aleatórios uniformemente distribuídos no intervalo $[-20, 20]$. Esses programas recebem no terceiro argumento uma semente para o gerador de números aleatórios.

Observação.  O programa RandomInts.java usa o tipo de dado SET<Integer>, que ainda não estudamos.

Exemplos de execução

$ java-introcs RandomInts 10 20 121 | java-introcs ThreeSum
elapsed time = 0.0
3
$ java-introcs RandomInts 10 20 121 | java-introcs ThreeSumBinary
elapsed time = 0.002
3
$ java-introcs RandomInts 10 20 121 | java-introcs ThreeSumQuad
elapsed time = 0.002
3
$

ThreeSumBinary.java pode ter saída incorreta quando há elementos repetidos:

$ java-introcs RandomIntsPlain 6 3 2023
-1 -2 3 2 2 0
$ java-introcs RandomIntsPlain 6 3 2023 | java-introcs ThreeSum
elapsed time = 0.0
3
$ java-introcs RandomIntsPlain 6 3 2023 | java-introcs ThreeSumBinary
elapsed time = 0.002
2
$

O programa ThreeSumBinaryDups.java é uma versão de ThreeSumBinary.java que permite elementos repetidos:

$ java-introcs RandomIntsPlain 6 3 2023 | java-introcs ThreeSumBinaryDups
elapsed time = 0.001
3
$

Desempenho.  Seu programa ThreeSumQuad.java deve ser muito mais rápido que ThreeSum.java:

$ java-introcs RandomIntsPlain 5000 100000 121 > tmp.txt
$ java-introcs ThreeSum < tmp.txt
elapsed time = 21.396
79379
$ java-introcs ThreeSumQuad < tmp.txt
elapsed time = 0.065
79379
$

Provavelmente seu ThreeSumQuad.java será um tanto mais rápido que ThreeSumBinaryDups.java:

$ java-introcs RandomIntsPlain 20000 100000 121 > tmp.txt
$ java-introcs ThreeSumBinaryDups < tmp.txt
elapsed time = 11.03
5006256
$ java-introcs ThreeSumQuad < tmp.txt
elapsed time = 0.666
5006256
$

Doubling test.  Usando o doubling test é possível ter uma ideia da complexidade dos vários algoritmos (veja o código do programa DTestWRepeats.java para interpretar as saídas abaixo):

$ java-introcs DTestWRepeats 0 512 2023
Algorithm: N^3
  size   time ratio
   512   0.02  0.71
  1024   0.19  7.83
  2048   1.48  7.85
  4096  11.75  7.97
  8192  95.01  8.08
[...]
$ java-introcs DTestWRepeats 1 512 2023
Algorithm: N^2\log N
  size   time ratio
   512   0.01  0.32
  1024   0.02  3.67
  2048   0.07  3.32
  4096   0.36  4.88
  8192   1.60  4.49
 16384   7.26  4.53
 32768  31.48  4.34
 65536 141.49  4.50
[...]
$ java-introcs DTestWRepeats 2 512 2023
Algorithm: N^2
  size   time ratio
   512   0.00  0.25
  1024   0.00  4.00
  2048   0.02  4.00
  4096   0.04  2.38
  8192   0.14  3.79
 16384   0.57  3.97
 32768   2.34  4.09
 65536   8.33  3.57
131072  31.59  3.79
262144 131.48  4.16
[...]
$ ls output*
output0.out output1.out output2.out
$ cat output*
95
88
696
5233
42722
343531
95
88
696
[...]
$

Entrega.  Neste exercício, basta você entregar seu programa ThreeSumQuad.java.