Java Reference
In-Depth Information
worst case for union-by-rank
and path compression
24.6
When both heuristics are used, the algorithm is almost linear in the worst
case. Specifically, the time required to process a sequence of at most
N
- 1
union
operations and
M
find
operations in the worst case is
Θ
(
M
α
(
M, N
))
(provided that
M
N
), where
α
(
M, N
) is a functional inverse of
Ackermann's
function,
which grows very quickly and is defined as follows:
3
≥
2
j
j
≥
1
A
1
j
(
,
)
=
≥
ij
i
2
Ai
1
(
,
)
=
A
(
i
-
12)
,
,
≥
2
Aij
,()
=
A
(
i
-
1
Aij
1
,
(
,
-
)
)
From the preceding, we define
α
(
MN
,
)
=
min
{
i
≥
1(
Ai MN
(
,
⁄
)
>
log
N
)
}
You might want to compute some values, but for all practical purposes,
α
(
M, N
)
Ackermann's func-
tion
grows very
quickly, and its
inverse is essen-
tially at most 4.
≤
4, which is all that really matters here. For instance, for any
j
> 1,
we have
A
2
j
(
,
)
=
A
1
A
2
j
(
,
(
,
-
1
)
)
2
A
2
j
(
,
-
1
)
=
2
2
2
2…
=
where the number of 2s in the exponent is
j
. The function
F
(
N
) =
A
(2,
N
) is
commonly called a
single-variable Ackermann's function
. The single-variable
inverse of Ackermann's function, sometimes written as log*
N,
is the number
of times the logarithm of
N
needs to be applied until
N
1. Thus log*65536 = 4,
because log log log log 65536 = 1, and log*2
65536
= 5. However, keep in mind
that 2
65536
has more than 20,000 digits. The function
α
(
M, N
) grows even
slower than log*
N
. For instance,
A
(3, 1) =
A
(2, 2) = 2
2
2
= 16. Thus for
N
< 2
16
,
α
(
M, N
)
≤
3. Further, because
A
(4, 1) =
A
(3, 2) =
A
(2,
A
(3, 1)) =
A
(2, 16), which
is 2 raised to a power of 16 stacked 2s, in practice,
α
(
M, N
)
≤
4. However,
α
(
M, N
) is
not a constant when
M
is slightly more than
N,
so the running time is not linear.
4
≤
3. Ackermann's function is frequently defined with
A
(1,
j
) =
j
+ 1 for
j
≥ 1. The form we use in
this text grows faster; thus the inverse grows more slowly.
4. Note, however, that if
M
=
N
log*
N,
then α(
M, N
) is at most 2. Thus, so long as
M
is slightly
more than linear, the running time is linear in
M
.
Search WWH ::
Custom Search