CCM0128 - Computação II (2025i)

Seja \(a\) um vetor de inteiros e $N=a.\textit{length}$. O par de índices $(i,j)$ com $0\leq i<j<N$ é uma inversão em $a$ se $a[i]>a[j]$. Se $(i,j)$ é uma tal inversão, dizemos que $j$ é uma inversão à direita de $i$ e que $i$ é uma inversão à esquerda de $j$.

O programa InvsDetailedBrute.java.  Considere o vetor $a=\{8, 7, 8, 2, 5, 3, 7, 7\}$. Note que $N = 8$. Podemos usar o programa InvsDetailedBrute.java dado abaixo para verificar o número de inversões à esquerda e à direita para cada $0\leq i<N$:

$ echo 8 7 8 2 5 3 7 7 | java-introcs InvsDetailedBrute +
8 7 8 2 5 3 7 7
0 1 0 3 3 4 2 2
6 3 5 0 1 0 0 0
6 4 5 3 4 4 2 2
Total: 15
Elapsed time: 0.0
$

Note que $a[i]=7$ quando $i=1$. Na saída acima, vemos que $i=1$ tem uma inversão à esquerda ($8>7$) e três inversões à direita ($7>2$, $7>5$ e $7>3$), dando um total de quatro inversões em que $i=1$ participa. Outro exemplo: $i=2$ tem $0$ inversões à esquerda e $5$ inversões à direita. Há um total de $15$ inversões em $a$.

Complexidade de tempo e o programa Inversions.java.  É imediato que o programa InvsDetailedBrute.java tem tempo de execução $\Theta(N^2)$. O programa Inversions.java (também dado abaixo) determina o número total de inversões em uma sequência dada.

$ echo 8 7 8 2 5 3 7 7 | java-introcs Inversions
15
15
$

(Veja o código de Inversions.java para entender por que a saída "aparece repetida".)

O que é interessante é que Inversions.java (mais precisamente, as funções count() em Inversions.java) tem tempo de execução $O(N\log N)$. A diferença entre os tempos de execução de InvsDetailedBrute.java e Inversions.java para entradas grandes é evidente no exemplo abaixo (Generate.java é também dado abaixo):

$ java-introcs Generate 100000 1000000 314 > 100000.txt
$ java-introcs InvsDetailedBrute < 100000.txt
Total: 2499871189
Elapsed time: 14.669
$ time java-introcs Inversions < 100000.txt
2499871189
2499871189

real 0m0.647s
user 0m0.688s
sys 0m0.152s
$

Sua tarefa.  Neste exercício, você deve escrever um programa chamado InvsDetailed.java que produz exatamente a mesma saída que InvsDetailedBrute.java, mas que tem tempo de execução $O(N\log N)$. O main() de seu programa InvsDetailed.java deve ser idêntico ao main() de InvsDetailedBrute.java. O que você deve fazer é reescrever o resto de InvsDetailedBrute.java. (Sugestão óbvia: estude Inversions.java!)

Verificação.  Para verificar a correção de seu programa InvsDetailed.java, você pode comparar sua saída com a saída de InvsDetailedBrute.java:

$ echo 8 7 8 2 5 3 7 7 1 2 8 | java-introcs InvsDetailedBrute +
8 7 8 2 5 3 7 7 1 2 8
0 1 0 3 3 4 2 2 8 7 0
8 5 7 1 3 2 2 2 0 0 0
8 6 7 4 6 6 4 4 8 7 0
Total: 30
Elapsed time: 0.0
$ echo 8 7 8 2 5 3 7 7 1 2 8 | java-introcs InvsDetailed +
8 7 8 2 5 3 7 7 1 2 8
0 1 0 3 3 4 2 2 8 7 0
8 5 7 1 3 2 2 2 0 0 0
8 6 7 4 6 6 4 4 8 7 0
Total: 30
Elapsed time: 0.0
$

Você pode usar Generate.java para gerar entradas maiores facilmente. No caso de entradas grandes, a saída é também grande. Para comparar tais saídas grandes de forma simples, você pode usar o programa md5 (md5sum no GNU/Linux).

$ java-introcs Generate 100000 1000000 88888888 | java-introcs InvsDetailedBrute + | md5
Elapsed time: 14.371
a0e3dafb9966c4dcf137f2c8a6c98691
$ java-introcs Generate 100000 1000000 88888888 | java-introcs InvsDetailed + | md5
Elapsed time: 0.024
a0e3dafb9966c4dcf137f2c8a6c98691
$

Leia sobre md5 na Wikipedia (muito brevemente: se dois strings são diferentes, "muito provavelmente" seus md5 são diferentes; dito de outra forma, se dois strings têm o mesmo md5, então "provavelmente" eles são o mesmo string).

Entrega.  Neste exercício, basta entregar seu programa InvsDetailed.java.