Database Reference
In-Depth Information
The worst time occurs if the computed split point is always at one side
(leaving just 2 points on one side), rather than the middle. The recurrence
is
n
2
) We must stop after
T
(
n
)=
T
(
n −
2) +
θ
(
K
iterations, giving a time
n
2
K
of
O
(
).
Sliding Windows.
For this algorithm, we compute best segments for
larger and larger windows, going from 2 up to at most
cL
(by the assumption
we discussed above). The maximum time to compute a single segment is
cL
i
=2
θ
L
2
). The number of segments can be as few as
(
i
)=
θ
(
n/cL
=
K/c
L
2
K
or as many as
K
. The time is thus
θ
(
)or
θ
(
Ln
). This is both a best
case and worst case bound.
Bottom-Up.
The first iteration computes the segment through each
pair of points and the costs of merging adjacent segments. This is easily
seen to take
O
(
n
) time. In the following iterations, we look up the minimum
error pair
S
new
;
delete from a heap (keeping track of costs is best done with a heap) the
costs of merging segments
i
and
i
+ 1 to merge; merge the pair into a new segment
i −
1and
i
and merging segments
i
+1 and
i
+2;
compute the costs of merging
S
i
−
2
;andinsert
these costs into our heap of costs. The time to look up the best cost is
S
new
with
S
i
−
1
and with
θ
(1)
and the time to add and delete costs from the heap is
O
(log
n
). (The time
to construct the heap is
).)
In the best case, the merged segments always have about equal length,
and the final segments have length
O
(
n
. The time to merge a set of length 2
segments, which will end up being one length
L
L
segment, into half as many
segments is
) (for the time to compute the best segment for every pair
of merged segments), not counting heap operations. Each iteration takes
the same time repeating
θ
(
L
θ
(log
L
) times gives a segment of size
L
.
The number of times we produce length
L
segments is
K
, so the total
time is Ω(
KL
log
L
)=Ω(
n
log
n/K
). The heap operations may take as
much as
).
In the worst case, the merges always involve a short and long segment,
and the final segments are mostly of length
O
(
n
log
n
). For a lower bound we have proven just Ω(
n
log
n/K
. The time to compute the
cost of merging a length 2 segment with a length
cL
i
segment is
θ
(
i
), and the
segment is
cL
L
2
). There are at most
time to reach a length
cL
i
=2
θ
(
i
)=
θ
(
L
2
)=
n/cL
).
(Time for heap operations is inconsequential.) This complexity study is
summarized in Table 5.
In addition to the time complexity there are other features a practitioner
might consider when choosing an algorithm. First there is the question of
such segments to compute, so the time is
n/cL × θ
(
O
(
Ln
