O que é um bom algoritmo de classificação de casos especiais?

13

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?

Zachary Vance
fonte
1
Você pode fazer uma pergunta mais precisa? Seu primeiro parágrafo pode ser lido para indicar que seus dados já estão classificados! Qual é exatamente a sua entrada e qual saída você deseja?
Jacques Carette
1
Sim, o idioma é um pouco confuso. Levei algum tempo para perceber que o conjunto de dados consiste em n números a serem classificados, mas esses números são organizados em uma grade sqrt (n) x sqrt (n), de modo que cada linha e cada coluna já esteja classificada. É isso que você quis dizer?
Sim, foi o que eu quis dizer. Vou editar para maior clareza.
Zachary Vance

Respostas:

19

É 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.

David Eppstein
fonte
A outra resposta fornece um algoritmo explícito com essa complexidade; portanto, considerarei esse problema resolvido para grades 2-D e, sem realmente verificar, provavelmente para grades de dimensões arbitrárias.
Zachary Vance
4

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.

Paulo
fonte
Em resumo, você pode fazer uma mesclagem de sqrt (N) -way, como no mergesort? Esse foi o meu melhor método de execução, mas acabou sendo O (N log N) - não tenho uma constante exata lá, mas há pelo menos 0,5 para log (sqrt (N)).
Zachary Vance