Precomputation: Difference between revisions

Revision as of 00:34, 28 December 2010

Revision as of 01:17, 28 December 2010

Line 1:

'''Precomputation''' is the use in an [[algorithm]] of a (typically relatively expensive) initial [[computation]], the results of which are then used to speed up later parts of that algorithm. The precomputation step may sometimes be expensive, and may often generate large [[data structure]]s as a result, but can be used to greatly reduce the effort required in the later stage.

Precomputing a set of intermediate results at the beginning of an algorithm's execution can often increase [[algorithmic efficiency]] substantially. This becomes advantageous when one or more inputs is constrained to a small enough range that the results can be stored in a reasonably sized block of memory. Because memory access is essentially constant in time complexity (except for [[cache|caching]] delays), any algorithm with a component which has worse than constant efficiency over a small input range can be improved by precomputing values. In some cases efficient approximation algorithms can be obtained by computing a [[Discrete mathematics|discrete]] subset of values and [[interpolating]] for intermediate input values, since interpolation is also a linear operation.