Contando pares de inversão

14

Uma aplicação clássica de dividir e conquistar é resolver o seguinte problema:

Dada uma matriz de elementos distintos e comparáveis, conte o número de pares de inversão na matriz: pares modo que e .a[1n](i,j)a[i]>a[j]i<j

Uma abordagem para isso é fazer uma classificação de mesclagem, mas também contar o número de pares de inversão nos subproblemas. Durante a etapa de mesclagem, contamos o número de pares de inversão que se estendem pelos (dois) subproblemas e aumentam as contagens dos subproblemas.

Enquanto isso é bom e fornece um algoritmo de tempo , isso atrapalha a matriz.O(nlogn)

Se tivermos a restrição adicional de que a matriz é somente leitura, podemos fazer uma cópia e lidar com a cópia ou usar uma estrutura de dados adicional, como uma árvore binária balanceada de estatísticas de ordem para fazer a contagem, ambas as quais usam Θ(n) Espaço teta (n) .

A questão atual é tentar melhorar o espaço, sem afetar o tempo de execução. ie

Existe um algoritmo de tempo O(nlogn) para contar o número de pares de inversão, que funciona em uma matriz somente leitura e usa espaço sub-linear (isto é, o(n) )?

Suponha um modelo de RAM de custo uniforme e que os elementos O(1) espaço O (1) e a comparação entre eles seja O(1) .

Uma referência serve, mas uma explicação será melhor :-)

Tentei pesquisar na web, mas não consegui encontrar nenhuma resposta positiva / negativa para isso. Suponho que isso seja apenas uma curiosidade.

Aryabhata
fonte
3
Chan e Pătraşcu fornecem um algoritmo de tempo , mas, tanto quanto posso ver ao escanear o papel, eles precisam de espaço . Ω ( n )o(nregistron)Ω(n)
Raphael
2
Além disso, Ajtai et al. provar que qualquer algoritmo (exato) de tempo de fluxo precisa de Ω ( n ) espaço. Parece haver aproximações que atendem aos seus critérios. O(n)Ω(n)
Raphael
1
@Raphael: Obrigado! Se não houver resposta, seu comentário seria a melhor resposta até o momento.
Aryabhata
BTW Estou um pouco confuso sobre esse limite inferior de Ajtai e cols. Teorema 8 diz "qualquer algoritmo", mas o limite inferior para mim parece ser contra a única passagem exata streaming de algoritmos, um modelo muito restrito
Sasho Nikolov
@ShohoNikolov: Eu acho que eles definiram globalmente seu modelo para algoritmos de streaming, então "any" seria restrito a eles. Espero que meu corolário - qualquer algoritmo exato de tempo - esteja correto, ou seja, que qualquer algoritmo de tempo linear possa ser expresso como um algoritmo de fluxo contínuo com muitas passagens constantes. Veremos . O(n)
Raphael

Respostas:

3

Aqui está a resposta de Rafael:

Chan e Pătraşcu fornecem um algoritmo de tempo , mas, tanto quanto posso ver ao escanear o papel, eles precisam de Ω ( n ) espaço. Além disso, Ajtai et al. provar que qualquer algoritmo (exato) de O ( n ) tempo de fluxo precisa de Ω ( n ) espaço. Parece haver aproximações que atendem aos seus critérios.o(nregistron)Ω(n)O(n)Ω(n)

Yuval Filmus
fonte
Obrigado por fazer uma resposta. Vou dar um pouco mais de tempo. O tráfego parece estar aumentando.
Aryabhata