Contagem de Inversões

Um dos problemas mais clássicos de programação é a contagem de inversões em uma sequência. De maneira simples, seja \(S={a_1,a_2,...,a_n}\). Uma inversão em \(S\) é um par \((i,j)\), com \(i<j\), tal que \(a_i>a_j\). Sabendo disso, faça um programa que calcula o número de inversões em uma sequência \(S\).

A abordagem mais simples pra o problema é testar todos os possíveis pares \((i,j)\), incrementando um contador sempre que encontrarmos uma inversão. Se a sequência for representa por um vetor v de \(n\) posições, basta usar dois for para percorrermos todos os possíveis valores de \(i\) e, dentro deste, um outro, para percorrermos todos os valores de \(j\) maiores que \(i\). Para cada inversão encontrada, incrementamos o valor de resp. Veja:

            for(int i=0;i<n;i++)
                for(int j=i+1;j<n;j++)
                    if(v[i]>v[j]) resp++;

Note que o código acima tem complexidade \(O(n^2)\), pois tem dois for, um dentro do outro, cada um com número de repetições proporcional a \(n\). Entretanto, podemos resolver esse problema de uma maneira bem mais eficiente, usando divisão e conquista.

Em vez de trabalharmos com o vetor inteiro, vamos dividir o vetor ao meio e trabalhar com suas metades, que chamaremos de u1 e u2. As posições de índice \(0 \leq i < \frac{n}{2}\) pertencem a u1 e as posições de índice \(\frac{n}{2} \leq i < n\) pertencem a u2. Sejam inv1 e inv2 os números de inversões em u1 e em u2, respectivamente. Queremos saber o valor de inv, o número de inversões em v. Há três tipos de inversões \((i,j)\) em v: aquelas em que \(i\) e \(j\) estão ambos em u1, aquelas em que \(i\) e \(j\) estão ambos em u2 e aquelas em que \(i\) está em u1 e \(j\) está em u2. A quantidade de inversões do primeiro e segundo caso, somados, é inv1+inv2. Agora precisamos calcular o terceiro caso.

Note que cada par \((i,j)\) em que \(i\) está em u1 e \(j\) está em u2 configura uma inversão. Então, para cada elemento em u1, precisamos contar a quantidade de elementos em u2 que são menroes que ele, e a soma de tudo isso será a quantidade de inversões do terceiro caso. Vamos ordenar os vetores u1 e u2 e usar o algoritmo do merge sort para ordenar v. Note que, quando vamos unir as duas metades ordenadas do vetor, todos os elementos já inseridos são menores que os que ainda vamos inserir. Deste modo, se estou olhando para o elemento \(i\) de u1 e \(j\) de u2, e u1[i]>u2[j], então u1[i] também será maior que todos os $ elementos ainda não inseridos de u2

Visto isso, a contagem de inversões fica simples. Toda vez que inserimos um elemento de u2 no versão final ordenada de v, ele formará uma inversão com todos os elementos de u1 que ainda não foram adicionados, deste modo, basta adicionar a uma variável inv o número de elementos que ainda estão em u1. Por fim, a função retornará inv1+inv2+inv, e ainda deixará v ordenado.

São poucas as modificações que temos que fazer no merge sort para que ele conte as inversões em um vetor (e ainda o ordene!). Veja o código para melhor entendimento:

            #include <vector> // para o uso de vector
            // neste código, irei definir INF como 1 bilhão
            #define INF 1000000000
            // função merge_sort que ordena um vector v
            int merge_sort(vector<int> &v){
                // declaro inv, o total de inversões
                int inv=0;
                // se o tamanho de v for 1, não há inversões
                if(v.size()==1) return 0;
                // se não
                // declaro os vetore u1 e u2
                vector<int> u1, u2;
                // e faço cada um receber uma metade de v
                for(int i=0;i<v.size()/2;i++){
                    u1.push_back(v[i]);
                }
                for(int i=v.size()/2;i<v.size();i++){
                    u2.push_back(v[i]);
                }
                // ordeno u1 e u2
                // e adiciono a inv as inversões de cada metade do vetor
                inv+=merge_sort(u1);
                inv+=merge_sort(u2);
                // e adiciono INF ao final de cada um deles
                u1.push_back(INF);
                u2.push_back(INF);
                // declaro ini1 e ini2 com valore inicial zero
                int ini1=0, ini2=0;
                // percorro cada posição de v
                for(int i=0;i<v.size();i++){
                    // se o menor não usado de u1 for menor o mesmo em u2
                    if(u1[ini1]<=u2[ini2]){
                        // então o coloco em v
                        v[i]=u1[ini1];
                        // e incremento o valor de ini1
                        ini1++;
                    }
                    // caso contrário, faço o análogo com u2 e ini2
                    else{
                        v[i]=u2[ini2];
                        ini2++;
                        // não se esquecendo de adicionar o número de elementos em u1
                        // ao total deinversões em v
                        inv+=u1.size()-ini1-1;
                    }
                }
                // por fim, retorno a quantidade de inversões
                return inv;
            }

Como adicionamos apenas operações de complexidade constante ao merge sort, sua complexidade não será alterada, e então conseguimos calcular a quantidade de inversões do vetor em \(O(n \log n)\).

Back to top