数据结构研究的一个新方向

作     者：李万学 

作者机构：成都科技大学计算机系 

出 版 物：《计算机工程与应用》 (Computer Engineering and Applications)

年 卷 期：1990年第26卷第1期

页      面：44-50页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金 

主　　题：数据结构 时间复杂性 折算复杂性 

摘      要：在数据结构与算法的研究中,如何度量数据结构算法的性能是一个非常重要的问题。不同的度量标准,数据结构和算法的性能估价就不相同,从而也影响着研究和设计数据结构及其有关的算法的方向。针对最坏时间复杂性和平均复杂性在度量某些数据结构时与实际运行情况相差较大,***等人提出了一种折算复杂性(Amortized Computational Complexity)。本文综述由于这种新复杂性概念的引入,在两方面开辟的研究新方向,一个是对现有数据结构的折算分析,其中对自适应表的研究是最突出的。另一更重要方向是根据这个新的复杂性度量标准建立新的优秀的数据结构,文中列举了多项成果。