Cargando…
Listing all sorting reversals in quadratic time
We describe an average-case O(n(2)) algorithm to list all reversals on a signed permutation π that, when applied to π, produce a permutation that is closer to the identity. This algorithm is optimal in the sense that, the time it takes to write the list is Ω(n(2)) in the worst case.
| Autores principales: | , , |
|---|---|
| Formato: | Online Artículo Texto |
| Lenguaje: | English |
| Publicado: |
BioMed Central
2011
|
| Materias: | |
| Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3110122/ https://www.ncbi.nlm.nih.gov/pubmed/21504604 http://dx.doi.org/10.1186/1748-7188-6-11 |
| Sumario: | We describe an average-case O(n(2)) algorithm to list all reversals on a signed permutation π that, when applied to π, produce a permutation that is closer to the identity. This algorithm is optimal in the sense that, the time it takes to write the list is Ω(n(2)) in the worst case. |
|---|