| 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
| |
| dbo:wikiPageLength
|
- 20568 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| 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 | |
