Complexidade da aplicação de uma permutação no local

27

Para minha surpresa, não consegui encontrar artigos sobre isso - provavelmente procurei as palavras-chave erradas.

Então, temos uma matriz de qualquer coisa e uma função em seus índices; é uma permutação. $f$ $f$

Como reordenar a matriz de acordo com com memória e tempo de execução o mais próximo de $f$ $O(1)$ e ? $O(n)$

Existem condições adicionais quando essa tarefa se torna mais fácil? Por exemplo, quando conhecemos explicitamente uma função é o inverso de ? $g$ $f$

Conheço um algoritmo que segue ciclos e percorre um ciclo para cada índice para verificar se é o menos do seu ciclo, mas, novamente, ele tem o pior caso tempo de execução de , embora, em média, pareça se comportar melhor. .. $O(n^2)$

ds.algorithms co.combinatorics permutations jkff
fonte

Uma observação fácil: se não apenas a matriz dos itens, mas também a matriz que contém a função f é gravável, é fácil executar a tarefa em O (n) tempo usando O (1) registros inteiros O (1) (cada um com comprimento O ( log n) bits) e espaço adicional para um item, apenas seguindo cada ciclo. Mas isso não funciona se a função f for dada em um armazenamento somente leitura (ou f for fornecida apenas como um oráculo), o que eu acho que é uma suposição nesta pergunta.

Tsuyoshi Ito

23

Fich et al. 1995 :

tempo,

espaço. Ele também discute alguns casos especiais.

O (n \log n)

$O(n \log n)$

O (\log n)

$O(\log n)$

Jukka Suomela

Sim, estou assumindo que temos f como um oráculo.

JKFF

3

@JukkaSuomela, você deve transformar isso em uma resposta. Além disso, considerando que

é uma permutação arbitrária, um argumento de entropia simples produz

espaço e / ou tempo, então eu ficaria surpreso se você pudesse fazer melhor que

no tempo e no espaço.

f

$f$

O (n \log n)

$O( n \log n)$

O (n \log n)

$O(n \log n)$

usar o seguinte comando

4

$O(n \log n)$ $O( \log^{2} n )$

Opção 1: trapaceie comprimindo sua permutação em uma estrutura de dados sucinta, consulte Munro http://www.itu.dk/people/ssrao/icalp03-a.pdf .

Opção 2: use uma decomposição do ciclo principal para armazenar sucintamente o perm e use esse espaço extra para trapacear http://oeis.org/A186202

$O(n^2)$ $O(\#\text{cycles} * \log n)$ espaço.

$O(n^2 * \text{distinct}\_\text{cycle}\_\text{lengths})$ $O((\#\text{cycles}\_\text{with}\_\text{same}\_\text{size}) * \log n)$

$i = 1 .. n$ $p(i)$ $i$ $O(n^2)$ $O(\log n)$

Chad Brewbaker
fonte

n \log n

$n\log n$

O nº 5 usa menos espaço que o nº 0 por um fator de log (n).

precisa saber é o seguinte

1

Se você usar a representação de ciclo da permutação, precisará de 1 elemento de matriz adicional para armazenar o item que está sendo permutado no momento e poderá percorrer os ciclos nas piores operações O (N).

Phil
fonte

2

jkff já disse que conhece o algoritmo que segue o ciclo, então ele claramente quer que a própria permutação seja tratada como (perto de) uma caixa preta. Como ele aponta na pergunta, a conversão de uma caixa preta (quase) em representação de ciclo pode levar tempo O (n ^ 2).

Joshua Grochow

A caixa preta p (i) está correta. Você apenas percorre o ciclo até voltar ao i. O problema é de complexidade Kolomogorov para armazenar a lista de itens que foram atualizados, para que você não os alterne várias vezes. Munro tem limites nisso. itu.dk/people/ssrao/icalp03-a.pdf

Chad Brewbaker

-2

Qualquer permutação de N itens pode ser convertida em qualquer outra permutação usando trocas N-1 ou menos. O pior caso para esse método pode exigir chamadas O (n ^ 2) para o seu oráculo, F (). Comece da menor posição. Seja x a posição que estamos trocando no momento.

Se F (x)> = x, troque as posições x e F (x). Senão, precisamos descobrir onde o item que estava na posição F (x) está atualmente na lista. Podemos fazer isso com a seguinte iteração. Seja y = F (x). Faça até y> = x: y = F (y): Finalize Do. Agora troque as posições x e y.

Russell Easterly
fonte

3

O (n^{2})

$O(n^2)$

Desculpe. Eu sou novo nesse grupo. Eu gosto deste método devido à sua simplicidade. Às vezes, encontro simplicidade mais rápido que eficiência. Conheço outro método que requer O (n) etapas, mas O (nlogn) espaço.

Russell Easterly

1

Russell, mesmo alocando e zerando o espaço O (n log n) já é O (n log n), você quis dizer na outra direção?

Jkff #

Você realmente não tem alocação e espaço zero. A idéia básica é quando F (x)> x precisamos lembrar onde colocamos o item na posição x. Para n realmente grande, eu usaria um banco de dados e apenas manteria um registro de onde o item x é movido. O registro pode ser excluído quando x chegar ao seu local final.

Russell Easterly

1

Mas por que você está dizendo que exige espaço O (n log n)?

Jkff 26/05

-2

Este método usa o inverso de F e requer n bits de armazenamento. Se x é a posição de um item na matriz original, seja G (x) a posição do item na matriz classificada. Seja B uma matriz de n bits. Defina todos os n bits de B como 0.

FOR x = 1 en-1: SE B (x) == 0 ENTÃO: y = G (x): ATÉ x == y: Troque as posições x e y: B (y) = 1: y = G ( y): LOOP: ENDIF: PRÓXIMO X

Esse método continua trocando o item atualmente na posição x para a posição final do item. O loop interno termina quando o item correto é trocado na posição x. Como cada troca move pelo menos um item para a posição final do item, o loop Do interno não pode exceder mais de n-1 vezes durante a execução. Eu acho que esse método é O (n) tempo e espaço.

Russell Easterly
fonte

2

Você já olhou o jornal? Os dois algoritmos que você lista aqui são os dois "óbvios". O artigo tem menos óbvias, com diferentes trocas no espaço-tempo, em particular muito menos espaço.

Yuval Filmus 26/05

Complexidade da aplicação de uma permutação no local

Respostas: