[go: up one dir, main page]

About: X + Y sorting

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

Unsolved problem in computer science: Is there an sorting algorithm faster than ? (more unsolved problems in computer science) In computer science, sorting is the problem of sorting pairs of numbers by their sums. Applications of the problem include transit fare minimisation, VLSI design, and sparse polynomial multiplication. As with comparison sorting and integer sorting more generally, algorithms for this problem can be based only on comparisons of these sums, or on other operations that work only when the inputs are small integers.

Property Value
dbo:abstract
  • Unsolved problem in computer science: Is there an sorting algorithm faster than ? (more unsolved problems in computer science) In computer science, sorting is the problem of sorting pairs of numbers by their sums. Applications of the problem include transit fare minimisation, VLSI design, and sparse polynomial multiplication. As with comparison sorting and integer sorting more generally, algorithms for this problem can be based only on comparisons of these sums, or on other operations that work only when the inputs are small integers. It is unknown whether this problem has a comparison-based solution whose running time is asymptotically faster than sorting an unstructured list of equally many items. Therefore, research on the problem has focused on two approaches to settle the question of whether such an improvement is possible: the development of algorithms that improve on unstructured sorting in their number of comparisons rather than in their total running time, and lower bounds for the number of comparisons based on counting cells in subdivisions of high-dimensional spaces. Both approaches are historically tied together, in that the first algorithms that used few comparisons were based on the weakness of the cell-counting lower bounds. (en)
  • 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. 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. (pt)
dbo:thumbnail
dbo:wikiPageID
  • 43934137 (xsd:integer)
dbo:wikiPageLength
  • 20568 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1116626728 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:subject
rdfs:comment
  • Unsolved problem in computer science: Is there an sorting algorithm faster than ? (more unsolved problems in computer science) In computer science, sorting is the problem of sorting pairs of numbers by their sums. Applications of the problem include transit fare minimisation, VLSI design, and sparse polynomial multiplication. As with comparison sorting and integer sorting more generally, algorithms for this problem can be based only on comparisons of these sums, or on other operations that work only when the inputs are small integers. (en)
  • 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. (pt)
rdfs:label
  • Ordenação X + Y (pt)
  • X + Y sorting (en)
owl:sameAs
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License