E09 Three sum deluxe improved
Na aula de 3/11/2021, discutimos novamente 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)$.
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)$. Também não é difícil ver que sua complexidade de pior caso é $\Omega(N^2\log N)$ (por exemplo, basta observar que esse algoritmo demora tempo $\Omega(N^2\log N)$ no caso em que não há triplas que somam zero). Assim, o programa ThreeSumDeluxe.java dado abaixo, que implementa esse algoritmo, tem complexidade de pior caso $\Theta(N^2\log N)$.
O programa ThreeSumDeluxe.java tem um problema: caso a sequência dada tenha elementos repetidos, ThreeSumDeluxe.java pode não dar a resposta certa.
Neste exercício, você deve melhorar ThreeSumDeluxe.java para que ele funcione corretamente para entradas com repetições. Seu programa melhorado deve chamar-se ThreeSumDeluxeImproved.java. Seu programa ThreeSumDeluxeImproved.java deve ter complexidade de pior caso $O(N^2\log N)$.
Elementos repetidos. O programa RandomIntsPlain.java pode ser usado para gerar entradas para o problema 3SUM:
$ java-introcs RandomIntsPlain 10 20 121
-8 17 7 9 17 -17 8 11 12 -4
$
No exemplo acima, 10 indica que queremos 10 inteiros e 20 indica que queremos números aleatórios uniformemente distribuídos no intervalo $[-20, 20]$. RandomIntsPlain.java recebe no terceiro argumento uma semente para o gerador de números aleatórios.
Como RandomIntsPlain.java gera sequências de inteiros com possíveis repetições, as saídas de ThreeSum.java e ThreeSumDeluxe.java com entradas geradas por RandomIntsPlain.java podem não coincidir:
$ java-introcs RandomIntsPlain 30 20 121 | java-introcs ThreeSum
elapsed time = 0.0
69
$ java-introcs RandomIntsPlain 30 20 121 | java-introcs ThreeSumDeluxe
elapsed time = 0.001
49
$
Seu programa ThreeSumDeluxeImproved.java deve ter a mesma saída que ThreeSum.java (mas, para valores maiores de $N$, seu programa deve ser bem mais rápido).
$ java-introcs RandomIntsPlain 5000 10000 121 | java-introcs ThreeSum
elapsed time = 21.605
793610
$ java-introcs RandomIntsPlain 5000 10000 121 | java-introcs ThreeSumDeluxeImproved
elapsed time = 0.634
793610
$ java-introcs RandomIntsPlain 10000 50000 121 | java-introcs ThreeSum
elapsed time = 173.801
1250900
$ java-introcs RandomIntsPlain 10000 50000 121 | java-introcs ThreeSumDeluxeImproved
elapsed time = 2.627
1250900
$
Gerador de entradas. Como visto acima, para gerar entradas com as quais experimentar seu programa ThreeSumImproved.java, você pode usar os programas RandomIntsPlain.java. Para gerar entradas sem repetição, você pode usar o programa RandomInts.java:
$ java-introcs RandomIntsPlain 10 20 121
-8 17 7 9 17 -17 8 11 12 -4
$ java-introcs RandomInts 10 20 121
-17 -8 -4 5 7 8 9 11 12 17
$
Observação. O programa RandomInts.java usa o tipo de dado SET, que ainda não estudamos.
Sugestão. Ao escrever seu programa ThreeSumDeluxeImproved.java, certifique-se inicialmente de que ele dá a resposta certa para entradas geradas por RandomInts.java. Ademais, compare o tempo de execução de ThreeSumDeluxe.java e de seu programa ThreeSumDeluxeImproved.java. Seu programa não deve demorar mais do que o dobro que ThreeSumDeluxe.java:
$ java-introcs RandomInts 10000 10000000 121 | java-introcs ThreeSumDeluxe
elapsed time = 1.743
6282
$ java-introcs RandomInts 10000 10000000 121 | java-introcs ThreeSumDeluxeImproved
elapsed time = 2.512
6282
$ java-introcs RandomInts 20000 10000000 121 | java-introcs ThreeSumDeluxe
elapsed time = 7.28
50050
$ java-introcs RandomInts 20000 10000000 121 | java-introcs ThreeSumDeluxeImproved
elapsed time = 11.001
50050
$ java-introcs RandomInts 40000 10000000 121 | java-introcs ThreeSumDeluxe
elapsed time = 30.14
398929
$ java-introcs RandomInts 40000 10000000 121 | java-introcs ThreeSumDeluxeImproved
elapsed time = 47.045
398929
$
Exemplos de execução. Seguem mais alguns exemplos de execução.
$ java-introcs RandomIntsPlain 10000 100000000 121 | java-introcs ThreeSumDeluxeImproved
elapsed time = 2.453
675
$ java-introcs RandomIntsPlain 20000 100000000 121 | java-introcs ThreeSumDeluxeImproved
elapsed time = 11.107
5101
$ java-introcs RandomIntsPlain 40000 100000000 121 | java-introcs ThreeSumDeluxeImproved
elapsed time = 48.288
39667
$ java-introcs RandomIntsPlain 80000 100000000 121 | java-introcs ThreeSumDeluxeImproved
elapsed time = 198.643
319900
$
Integer overflow. Tanto no programa ThreeSum.java como ThreeSumDeluxe.java, não nos preocupamos com integer overflow. Da mesma forma, você não precisa se preocupar com integer overflow em seu programa ThreeSumDeluxeImproved.java.
Entrega. Neste exercício, basta você entregar seu programa ThreeSumDeluxeImproved.java.
- 4 novembro 2021, 17:39 PM
- 4 novembro 2021, 17:39 PM
- 4 novembro 2021, 17:39 PM
- 4 novembro 2021, 17:39 PM