Space-time tradeoff
|
|
In computer science, a space-time tradeoff (also a time-memory tradeoff) can sometimes be made in the event of a shortage of either time or space. Some algorithms can be made to run in a shorter time if they use more memory space, and vice versa.
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.
For another example, bubble sort is a sort algorithm that uses O(1) (constant) memory space and O(n2) (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 attacks against cryptosystems. The meet-in-the-middle attack is an application of space-time tradeoffs.