Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
| amortized analysis | In an amortized analysis, the time required to perform a sequence of data-structure operations is averaged over all the operations performed. Guarantees the average performance of each operation in the worst case.
(See page 405)
|
 |
|
|
| aggregate analysis | for all n a sequence of n operations takes worst-case time T(n) in total.
(See page 406)
|
|
|
|
| amortized cost | average cost, T(n)/n. Applies to each operation, even when there are several types of operations in the sequence. The amount charged to an operation
(See page 406, 410)
|
|
|
|
| accounting method | In the accounting method of amortized analysis, we assign differing charges to different operations, with some operations charged more or less than they actually cost.
(See page 410)
|
|
|
|
| credit | When an operation's amortized cost exceeds its actual cost, the difference is assigned to specific objects in the data structure as credit. Credit can be used later on to help pay for operations whose amortized cost is less than their actual cost. Thus, the amortized cost of an operation is split between its actual cost and credit that is either deposited or used up.
(See page 410)
|
|
|
|
| potential method | A method of amortized analysis which represents the prepaid work as "potential energy" or just "potential," that can be released to pay for future operations. The potential is associated with the data structure as a whole rather than with specific objects within the data structure.
(See page 412)
|
|
|
|
| potential function | Φ - maps each data structure Di to a real number Φ(Di), which is the potential associated with data structure Di.
(See page 413)
|
|
|
|
| load factor | defines α(T) of a nonempty table T to be the number of items stored in the table divided by the size (number of slots) of the table.
(See page 417)
|
|
|
|
| expand | When an item is inserted into a full table, the expand function allocates a new table with more slots than the old table had. An example of expansion occurs when the procedure determines that a table T is full, then inserts all items in T into a new table, frees T, renames the new table to T, then inserts x into T.
(See page 417)
|
|
|
|
| elementary insertion | procedure which inserts all items in table[T] into new-table or inserts x into table[T]
(See page 418)
|
|
|
|
| contract | Table contraction is analogous to table expansion: when the number of items in the table drops too low, allocate a new, smaller table and then copy the items from the old table into the new one. The storage for the old table can then be freed by returning it to the memory-management system.
(See page 420)
|
|
|
|
| bit-reversal permutation | swaps elements whose indices have binary representations that are the reverse of each other.
(See page 425)
|
|
|
|
| α-balanced | property of a given node x if size[left[x]] ≤ α · size[x] and size[right[x]] ≤ α · size[x]. The tree as a whole is α-balanced if every node in the tree is α-balanced.
(See page 427)
|
|
|
|
| terminating case | once encountered, the loop terminates after a constant number of additional operations.
(See page 428)
|
|
|
|
| gossiping | communicating a unique item from each vertex in a graph to every other vertex
(See page 429)
|
2002 McGraw-Hill Higher Education