A self-organising feature map sorts n real numbers in O(n) time apparently violating the O(n log n) bound. Detailed analysis shows that the net takes advantage of the uniform distribution of the numbers and, in this case, sorting in O(n) is possible. There are, however, an exponentially small fraction of pathological distributions producing O(n^2) sorting time. It is interesting to observe that standard learning produced a smart sorting algorithm.
Sorting with Self-Organising Maps
BUDINICH, MARCO
1995-01-01
Abstract
A self-organising feature map sorts n real numbers in O(n) time apparently violating the O(n log n) bound. Detailed analysis shows that the net takes advantage of the uniform distribution of the numbers and, in this case, sorting in O(n) is possible. There are, however, an exponentially small fraction of pathological distributions producing O(n^2) sorting time. It is interesting to observe that standard learning produced a smart sorting algorithm.File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
