Amortized Computational Complexity
Amortized Computational Complexity
复制标题
DOI：
10.1137/0606031
复制
发表时间：
1985-04
期刊：
影响因子：
--
通讯作者：
R. Tarjan
中科院分区：
文献类型：
--
作者：
R. Tarjan
数据结构的复杂性分析中的一种强大的技术是摊销，或者随着时间的流逝，摊销时间是一种现实但稳健的复杂度度量。设计摊销复杂性较低的算法，我们获得了简单，灵活和有效的“自我调整”数据结构。几位研究人员关于摊销复杂性。
A powerful technique in the complexity analysis of data structures is amortization, or averaging over time. Amortized running time is a realistic but robust complexity measure for which we can obtain surprisingly tight upper and lower bounds on a variety of algorithms. By following the principle of designing algorithms whose amortized complexity is low, we obtain “self-adjusting” data structures that are simple, flexible and efficient. This paper surveys recent work by several researchers on amortized complexity.