Sorting is commonly meant as the task of arranging keys in increasing or decreasing order (or small variations of this order). Given n keys underlying a total order the best organization in an array is maintaining them in sorted order Searching requires Theta(log n) comparisons in the worst case, which is optimal. We demonstrate that this basic fact in data structures does not hold for the general case of multi-dimensional keys, whose comparison cost is proportional to their length. In two papers [1, 3] and the full version in [2], Andersson, Hagerup, Hastad and Petersson study the complexity of searching a sorted array of n keys, each of length k, arranged in lexicographic (or alphabetic) order for an arbitrary, possibly unbounded, ordered alphabet. They give sophisticated arguments for proving a tight bound in the worst case for this basic data organization, up to a constant factor obtaining [GRAPHICS] character comparisons (or probes). Note that the bound is Theta (log n) when k = 1, which is the case that is well known in algorithmics. We describe a novel permutation of the n keys that is different front the sorted order and sorting is just the starting point for describing our preprocessing. When keys are stored according to this "unsorted" order in the array, the complexity of searching drops to Theta (k + log, n) character comparisons (or probes) in the worst case, which is optimal among all possible permutations' of the n keys in the array, up to a constant factor Again, the bound is Theta(log n) when k = 1.
No sorting? Better searching! / Franceschini, Gianni; Roberto, Grossi. - STAMPA. - (2004), pp. 491-498. (Intervento presentato al convegno 45th Annual IEEE Symposium on Foundations of Computer Science tenutosi a Rome, ITALY nel OCT 17-19, 2004) [10.1109/focs.2004.43].
No sorting? Better searching!
FRANCESCHINI, GIANNI;
2004
Abstract
Sorting is commonly meant as the task of arranging keys in increasing or decreasing order (or small variations of this order). Given n keys underlying a total order the best organization in an array is maintaining them in sorted order Searching requires Theta(log n) comparisons in the worst case, which is optimal. We demonstrate that this basic fact in data structures does not hold for the general case of multi-dimensional keys, whose comparison cost is proportional to their length. In two papers [1, 3] and the full version in [2], Andersson, Hagerup, Hastad and Petersson study the complexity of searching a sorted array of n keys, each of length k, arranged in lexicographic (or alphabetic) order for an arbitrary, possibly unbounded, ordered alphabet. They give sophisticated arguments for proving a tight bound in the worst case for this basic data organization, up to a constant factor obtaining [GRAPHICS] character comparisons (or probes). Note that the bound is Theta (log n) when k = 1, which is the case that is well known in algorithmics. We describe a novel permutation of the n keys that is different front the sorted order and sorting is just the starting point for describing our preprocessing. When keys are stored according to this "unsorted" order in the array, the complexity of searching drops to Theta (k + log, n) character comparisons (or probes) in the worst case, which is optimal among all possible permutations' of the n keys in the array, up to a constant factor Again, the bound is Theta(log n) when k = 1.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
