Java Reference
In-Depth Information
partition, doing so would reduce the number of times that the while loop can be
further executed.
Our final example uses amortized analysis to prove a relationship between the
cost of the move-to-front self-organizing list heuristic from Section 9.2 and the cost
for the optimal static ordering of the list.
Recall that, for a series of search operations, the minimum cost for a static
list results when the list is sorted by frequency of access to its records. This is
the optimal ordering for the records if we never allow the positions of records to
change, because the most-frequently accessed record is first (and thus has least
cost), followed by the next most frequently accessed record, and so on.
Theorem14.2 The total number of comparisons required by any series S of n or
more searches on a self-organizing list of length n using the move-to-front heuristic
is never more than twice the total number of comparisons required when series S is
applied to the list stored in its optimal static order.
Proof: Each comparison of the search key with a record in the list is either suc-
cessful or unsuccessful. For m searches, there must be exactly m successful com-
parisons for both the self-organizing list and the static list. The total number of
unsuccessful comparisons in the self-organizing list is the sum, over all pairs of
distinct keys, of the number of unsuccessful comparisons made between that pair.
Consider a particular pair of keys A and B. For any sequence of searches S,
the total number of (unsuccessful) comparisons between A and B is identical to the
number of comparisons between A and B required for the subsequence of S made up
only of searches for A or B. Call this subsequence S AB . In other words, including
searches for other keys does not affect the relative position of A and B and so does
not affect the relative contribution to the total cost of the unsuccessful comparisons
between A and B.
The number of unsuccessful comparisons between A and B made by the move-
to-front heuristic on subsequence S AB is at most twice the number of unsuccessful
comparisons between A and B required when S AB is applied to the optimal static
ordering for the list. To see this, assume that S AB contains i As and j Bs, with i j.
Under the optimal static ordering, i unsuccessful comparisons are required because
B must appear before A in the list (because its access frequency is higher). Move-to-
front will yield an unsuccessful comparison whenever the request sequence changes
from A to B or from B to A. The total number of such changes possible is 2i because
each change involves an A and each A can be part of at most two changes.
Because the total number of unsuccessful comparisons required by move-to-
front for any given pair of keys is at most twice that required by the optimal static
ordering, the total number of unsuccessful comparisons required by move-to-front
for all pairs of keys is also at most twice as high. Because the number of successful
Search WWH ::




Custom Search