Boost logo

Boost :

From: Kevin Atkinson (kevina_at_[hidden])
Date: 2000-07-06 13:12:53

On Thu, 6 Jul 2000, Dietmar Kuehl wrote:

> I think the best algorithm (which also happens to be *much* simpler
> than a splay tree) uses O(n * inverse(Ackermann(n))) or something like
> this (don't nail me down on the details).

Which is about n log2*(n)

Where log2* is the iterative log function base 2. That is the number of
times it is necessary to apply log2 to n to get it below 1. This
function grows VERY slowly so it is considered to be nearly constant:

log2*(3) = 2
log2*(8 = 2^3) = 3
log2*(256 = 2^8) = 4
log2*(2^256) = 5

> The algorithm is rather
> simple: Individual elements, ie. set containing only on element, are
> represented by themselves and simply store a "pointer" to themselves.
> When uniting two sets, the pointer in one of the representives is
> replaced by the pointer to the other representative. When looking for
> a representative for a given element, the chain is walked up and the
> current pointers in the nodes encountered are replaced by a pointer to
> the representative (there are some variations on this and I don't know
> exactly which is theoretically or practically best approach; as far as
> I remember, these differ...). That's all.

This won't give the above performance. I will elaborate on the details
when I get home (so that I can look it up in my text book) if anyone is

Kevin Atkinson
kevina at users sourceforge net

Boost list run by bdawes at, gregod at, cpdaniel at, john at