集合上两个问题的复杂度下界及其最佳算法设计

The Complexity Lower Bound of Two Set Problems and Their Optimum Algorithms

本文利用下沉路径,上浮路径的概念在堆结构上分别给出了对具有几个元素的集合进行插入、删除一个元素的复杂度下界及其证明,结果为:插入一个元素最坏情况下至少需要 O(loglogn)次元素的比较;删除一个至少需要 O(logn)次元素的比较,与此同时,给出相应的最佳插入、删除算法.

The paper gives out the lower bound in inserting and deleting one element on the heapwhich is of n elements respectively and its identification by using the conceptions of descend-ing path and ascending path.The result is that it will spend at least O(loglog n)elementcomparisons in the worst case to insert one element into the heap,and it will spend at least O(log n)element comparisons to delete one element from the heap.Meanwhile,the best in-sert algorithm and delete algorithm are presented.