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. 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 math on 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. For another example, Bubble Sort is a Sort Algorithm that uses O (1) (constant) memory space and O(''n''2) (quadratic) time. In other words, its memory requirement is unrelated to the length of the list to be sorted, but its time requirement grows proportionally to the square of the length of the list. In the case of the sorting problem, a space-time tradeoff can be made by using a different algorithm such as Binary Tree Sort . Its memory requirement is O(''n'') (linear), but its time requirement is O(''n'' lg ''n'') ("linearithmic") which is optimal for a general sort algorithm. Binary tree sort's time requirement grows more slowly than bubble sort's, but its memory requirement grows faster. In the case of the sorting problem, all-around better algorithms exist, such as Heapsort , which combines the good qualities of bubble sort and binary tree sort: its time requirement is O(''n'' lg ''n''), and its memory requirement is O(1). 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
|
|
|