A General Lower Bound on the I/O-Complexity of Comparison-based Algorithms
A General Lower Bound on the I/O-Complexity of Comparison-based Algorithms
复制标题
基于比较的算法的 I/O 复杂度的一般下界
DOI：
--
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
Kirsten Larsen
中科院分区：
文献类型：
--
作者：
L. Arge;Mikael B. Knudsen;Kirsten Larsen
我们展示了解决给定问题所需的比较次数和I/O操作次数之间的一般关系。这种关系使人们能够显示下限的数量的I/O操作需要解决一个问题时，一个较低的边界上的数量的比较是已知的。我们使用的结果，显示下界的I/O复杂性的一些问题，已知的技术只给平凡的界限。其中包括从一个多重集合中删除重复项的问题，这是一个在关系数据库系统中非常重要的问题，以及确定一个多重集合的模式（最频繁出现的元素）的问题。我们开发这些问题的算法，以表明，下界是紧的。
We show a general relationship between the number of comparisons and the number of I/O-operations needed to solve a given problem. This relationship enables one to show lower bounds on the number of I/O-operations needed to solve a problem whenever a lower bound on the number of comparisons is known. We use the result to show lower bounds on the I/O-complexity on a number of problems where known techniques only give trivial bounds. Among these are the problems of removing duplicates from a multiset, a problem of great importance in e.g. relational data-base systems, and the problem of determining the mode — the most frequently occurring element — of a multiset. We develop algorithms for these problems in order to show that the lower bounds are tight.