Please enable JavaScript.
Coggle requires JavaScript to display documents.
Space and time trade-offs - Coggle Diagram
Space and time trade-offs
The idea is to preprocess the problem’s input,
in whole or in part, and store the additional information obtained to accelerate solving the problem afterward. We call this approach input enhancement
Counting methods for sorting
Boyer-Moore algorithm for string matching and its simplified version suggested by Horspool
The other type of technique that exploits space-for-time trade-offs simply uses
extra space to facilitate faster and/or more flexible access to the data. We call this
approach preprocessing
Preprocessing highlights two facets of this variation of the
space-for-time trade-off: some processing is done before a problem in question is actually solved but, unlike the input-enhancement variety, it deals with access
structuring
This approach is ilustrated by
Hashing
Indexing with B-trees
Another design technique related to the space-for-time
trade-off idea: dynamic programming
This strategy is based on recording solutions to overlapping subproblems of a given problem in a table from which a solution to the problem in question is then obtained
the two resources—time and space—do not
have to compete with each other in all design situations. In fact, they can align to bring an algorithmic solution that minimizes both the running time and the space
consumed
Such a situation arises, in particular, when an algorithm uses a space-efficient data structure to represent a problem’s input, which leads, in turn, to a
faster algorithm
It is also important to analyze data compression
In data compression, size reduction is the goal rather than a technique for solving another problem.
Hashing
The elements
of this set can be of an arbitrary nature: numbers, characters of some alphabet, character strings, and so on
assume that we have to implement
a dictionary of n records with keys K1, K2,...,Kn
Hashing is based on the idea of distributing keys among a one-dimensional
array H[0..m − 1] called a hash table
The distribution is done by computing, for
each of the keys, the value of some predefined function h called the hash function. This function assigns an integer between 0 and m − 1, called the hash address, to a key
A hash function needs to satisfy these requirements
A hash function needs to distribute keys among the cells of the hash table as
evenly as possible
A hash function has to be easy to compute
A hash table’s size should not be excessively large compared to the number of
keys, but it should be sufficient to not jeopardize the implementation’s time efficiency
Obviously, if we choose a hash table’s size m to be smaller than the number
of keys n, we will get collisions. But collisions should be
expected even if m is considerably larger than n. In fact, in the worst case, all the keys could be hashed to the same cell
of the hash table
Fortunately, with an appropriately chosen hash table size and a
good hash function, this situation happens very rarely. Still, every hashing scheme
must have a collision resolution mechanism. This mechanism is different in the two principal versions of hashing
Open hashing
1 more item...
Closed hashing
1 more item...
Double hashing is superior to linear probing. But its performance also deteriorates when the table gets close to being full. A natural solution in such a situation is rehashing: the current
table is scanned, and all its keys are relocated into a larger table
A variation of hashing is the extendible hashing
A location computed by a hash function in extendible hashing indicates a disk address of a bucket that can hold up to b keys. When a key’s bucket is identified, all its keys are read into main memory and then searched for the key in question