Ordenação X + Y
Em ciência da computação, ordenação X + Y é o problema de ordenação de pares de números por sua soma. Dados dois conjuntos finitos X e Y, o problema é ordenar todos os pares x ∈ X, y ∈ Y pela chave x + y. O problema é atribuído a Elwyn Berlekamp.[1][2]
O problema pode ser resolvido usando ordenação por comparação em tempo O(nm log(nm)) para conjuntos de tamanhos n e m, ou O(n² log n²) = O(n² log n) quando é assumido que m = n. Este é também o melhor limite conhecido para o problema, mas se a ordenação X + Y pode ser feita estritamente mais rápida que a ordenação de números arbitrários n×m é um problema aberto.[3][2]
Referências[editar | editar código-fonte]
- ↑ Harper, L. H.; Payne, T.H.; Savage, J. E.; Straus, E. (1975). «Sorting X + Y». Communications of the ACM. 18 (6): 347–349
- ↑ a b Demaine, Erik; Erickson, Jeff; O'Rourke, Joseph (20 de agosto de 2006). «Problem 41: Sorting X + Y (Pairwise Sums)». The Open Problems Project. Consultado em 23 de setembro de 2014
- ↑ Skiena, Steven (2008). The Algorithm Design Manual. [S.l.]: Springer. p. 119. doi:10.1007/978-1-84800-070-4_4