ISSN:
1436-5057
Keywords:
68Q05
;
68Q25
;
Analysis of algorithms
;
sorting
;
comparisons
;
lower bound
;
heapsort
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung Dieser Artikel untersucht die Komplexität von Heapsort Algorithmen für willkürliche Eingaben. Es wird bewiesen, daß für die Anzahl der Vergleiche auf jeden Fall eine untere Schranke vom Typ nlogn-O(n) gilt, und zwar in einr Klasse von Heapsort Algorithmen, die den Williams-Floyd-Algorithmus, den Carlsson-Algorithmus mit linearem oder binärem Einfügen und alle up-down Algorithmen enthält.
Notes:
Abstract The performance of Heapsort algorithms on arbitrary input is examined. It is proved that ann logn−O(n) lower bound on the number of comparisons holds for a set of Heapsort algorithms, including Williams-Floyd's algorithm, Carlsson's bottom-up linear or binary insertion algorithm, and all up-down algorithms, on any input.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02238646
Permalink
