期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1995
卷号：1995
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Consider a problem involving updates and queries of a data structure.
Assume that there exists a family of algorithms which exhibit a
tradeoff between query and update time. We demonstrate a general
technique of constructing from such a family
a single algorithm with best amortized time. We indicate some applications
of this technique.
On the other hand, when a given algorithm achieves similar
amortized performance, we may be able to obtain from it a family
of algorithms that exhibit the underlying tradeoff. We exemplify this by
a family of union-find algorithms trading union time for find time.
The algorithms are obtained in a simple way from the well known path
compression algorithm.
