Information AboutSpace-time Tradeoff |
|
change — hard drive space has for some time been getting cheaper at a much faster rate than other components of computers — the appropriate choices for space-time tradeoffs have changed radically. Often, by exploiting a time-memory tradeoff, the Complexity Class of a problem can be changed altogether. The most common situation is an algorithm involving a Lookup Table : an implementation can include the entire table, which reduces computing time, but increases the amount of memory needed, or it can compute table entries as needed, increasing computing time, but reducing memory requirements. A space-time tradeoff can be applied to the simple problem of data storage. If data is stored uncompressed, it takes more space but less time than if the data were stored compressed (since compressing the data reduces the amount of space it takes, but it takes time to run the Compression Algorithm ). Depending on the particular instance of the problem, either way is practical. Another example is displaying mathematical formulae on primarily text-based websites, such as Wikipedia . Storing only the LaTeX source and rendering it as an image every time the page was requested would be trading time for memory - more time used, but less memory. Rendering the image when the page was saved and storing the rendered images would be trading memory for time - more memory used, but less time. Algorithms that make use of space-time tradeoffs to achieve better running times include the Baby-step Giant-step algorithm for calculating discrete logarithms. In other areas, space-time tradeoffs can be made when performing Brute Force Attack s against Cryptosystem s through the creation of Rainbow Table s. The Meet-in-the-middle Attack is an application of space-time tradeoffs. EXTERNAL LINKS
|
|
|