On the average behavior of set merging algorithms (Extended Abstract)

摘要

In this paper we study the expected running time of a variety of algorithms that perform set merging. The set merging problem (for example, see AHU [1]) is concerned with using suitable data structures to represent partition of a set S &equil; { 1,2, .... ,n} so that a sequence of instructions of the form "x &Xgr; y", meaning

"Find the subset containing x; Find the subset containing y; Merge the two subsets if they are different."

may be carried out efficiently. Several alternative data structures for solving this problem are known, and their worse-case complexity fairly well understood [3], [4], [5], [8]. In contrast, the average behavior of even the most basic of these schemes remains an open problem [6]. It is the purpose of the present paper to determine the average behavior for several of the set merging algorithms commonly known.