Information Technology Reference
In-Depth Information
b
:=
0;
for
j:=
1
to
n/S
{
b
=(
j
−
1
)
S
on the
j
th iteration.
}
begin
for
i:=
1
to
S
C
[
i
]:=
0;
for
i:=
1
to
n
if
b
≤
x
i
≤
b
+
S
then
begin
k
:=
x
i
−
b
;
if
C
[
k
]
<
2
then
C
[
k
]
:=
C
[
k
]+
1;
end
;
for
i:=
1
to
S
if
C
[
i
]=
1
then print
b
+
i
;
b
:=
b
+
S
;
end
Figure 10.22
A RAM program for the unique-elements problem over the set
{
1, 2,
...
,
n}
when
n ≥ S ≥ O
(log
n
)
. The input to the program is the
n
-tuple
x
in which
x
i
is the
i
th
entry. The program uses space
O
(
S
)
.
Invoking Theorem
10.11.1
, we have a quadratic space-time product lower bound. The
RAM program for the unique elements problem given in Fig.
10.22
can be converted to a
branching program to obtain an upper bound on the space-time product needed for this
problem, as shown in Theorem
10.13.8
.
THEOREM
10.13.8
Let
|R| ≥ n
. There is an integer
n
0
>
0
such that for
n ≥ n
0
and
S
=Ω(log
n
)
the time
T
and space
S
used by any general branching program for the unique
elements function
f
(
n
)
2
R
n
must satisfy
n
unique
:
R
→
ST
=Ω(
n
2
)
This lower bound can be met to within a constant multiplicative factor for inputs drawn from the
set
{
1, 2, 3,
...
,
n
}
.
Proof
The lower bound follows directly from Theorem
10.11.1
. The upper bound follows
from an analysis of the branching program that results from conversion of the RAM program
in Fig.
10.22
.TheRAMprogrammakes
passes over the input data. On the
j
th pass
the program examines input values in the range
[(
j
n/S
1
)
S
,
...
,
jS
]
and determines for each
value whether there are zero, one, or more than one instances of it in the input.
The program uses an
S
-element one-dimensional array
C
[
1
..S
]
that it initializes to zero
at the beginning of each pass. If on the
j
th pass the
i
th input variable,
x
i
,isintheinterval
[(
j
−
1
)
S
]
,is
incremented unless it already has value 2. At the end of the
j
th pass, if the array element
C
[
i
]
has value 1, the program prints out the value
jS
+
i
, namely, the value of an input that
appears only once in the input.
−
1
)
S
,
...
,
jS
]
, the array element associated with it, namely
C
[
x
i
−
(
j
−
Search WWH ::
Custom Search