Eu tenho um conjunto de dados que é um número de objetos organizados em uma grade 2-D. Sei que tenho uma ordem estrita, aumentando à medida que você vai da esquerda para a direita em cada linha e aumentando de cima para baixo em cada coluna. Por exemplo,
- 1 2 3
- 4 6 7
- 5 8 9
Posso melhorar a classificação ingênua para classificar todo o conjunto de dados linearmente (conforme medido nas comparações)?
E os conjuntos de dados nd? Conjuntos de dados finitos arbitrários com um subconjunto de comparações conhecido?
ds.algorithms
total-ordering
sorting
Zachary Vance
fonte
fonte
Respostas:
É fácil provar um limite inferior de Ω (n 2 log n) para esse problema (no modelo de classificação por comparação): se o elemento na posição (i, j) estiver sempre dentro da distância 1/2 de i + j, então a grade as diagonais são independentes uma da outra e a ordem classificada em cada diagonal da grade é arbitrária. Portanto, sob essa restrição, o número total de pedidos possível é o produto (em todas as diagonais da grade) dos fatoriais dos comprimentos das diagonais, o que é exponencial em n 2 log n.
O que significa que os algoritmos padrão de classificação por comparação são assintoticamente ideais para grades ordenadas conforme você descreve.
fonte
Se eu entendi o problema corretamente (e talvez não, sinta-se à vontade para me dizer se não o faz), você deseja transformar uma grade 2D em uma matriz 1D classificada, enquanto cada linha e coluna já está classificada na grade 2D?
O primeiro elemento da lista nesse caso deve ser o canto superior esquerdo ((0,0), por definição do problema). Depois disso, ele deve ser o elemento (1,0) ou (0,1), pois todos os outros serão maiores que estes por definição.
Você pode generalizar dizendo que o próximo elemento menor da grade está sempre diretamente abaixo de um elemento já usado (ou na borda da grade) e também à direita de um elemento já usado (ou na borda da grade), pois ambos são definido como menor que ele. Portanto, a cada iteração, você deve considerar apenas o menor valor que atenda a esse requisito.
Você pode manter os possíveis candidatos na ordem classificada conforme os encontra (nunca mais de dois serão disponibilizados em uma iteração) e, a cada iteração, verifique os novos valores disponibilizados (se houver). Se eles forem inferiores ao menor dos candidatos anteriores, adicione-os à lista imediatamente e repita; caso contrário, adicione o candidato anterior mais baixo e compare com o próximo mais baixo etc.
Infelizmente, não pretendo fornecer uma complexidade exata disso, nem reivindico que seja a mais eficiente possível, certamente parece melhor do que uma abordagem ingênua, e espero que tenha explicado bem o suficiente para você entender.
EDIT: Para nd grades como essa, acredito que o mesmo princípio básico se aplica, mas cada iteração disponibiliza até n novos candidatos disponíveis e esses candidatos devem ser os menores elementos não utilizados em cada uma das n dimensões neste momento.
fonte