Please enable JavaScript.
Coggle requires JavaScript to display documents.
Space and Time Trade-Offs - Coggle Diagram
Space and Time Trade-Offs
input enhancement or preprocessing or preconditioning.
Sorting by Counting
comparison-counting sort
distribution counting
Input Enhancement in String Matching
pattern
text
Horspool’s Algorithm
Step 1: For a given pattern of length m and the alphabet used in both the pattern and text, construct the shift table as described above.
Step 2: Align the pattern against the beginning of the text.
Step 3: Repeat the following until either a matching substring is found or the pattern reaches beyond the last character of the text. Starting with the last character in the pattern, compare the corresponding characters in the pattern and text until either all m characters are matched (then stop) or a mismatching pair is encountered. In the latter case, retrieve the entry t (c) from the c’s column of the shift table where c is the text’s character currently aligned against the last character of the pattern, and shift the pattern by t (c) characters to the right along the text.
Boyer-Moore Algorithm
bad-symbol shift
good-suffix shift
Step 1: For a given pattern and the alphabet used in both the pattern and the text, construct the bad-symbol shift table as described earlier.
Step 2: Using the pattern, construct the good-suffix shift table as described earlier.
Step 3: Align the pattern against the beginning of the text.
Step 4 Repeat the following step until either a matching substring is found or the pattern reaches beyond the last character of the text.
prestructuring
hashing
key
Hashing is based on the idea of distributing keys among a one-dimensional array
hash table
hash function
hash address
open hashing or separate chaining
load factor
closed hashing or open addressing
linear probing
cluster
double hashing
rehashing
Asymptotic time efficiency With hashing, searching, insertion, and deletion can be implemented to take (1)time on the average but (n)time in the very unlikely worst case. For balanced search trees, the average time efficiencies are (log n) for both the average and worst cases.
Ordering preservation Unlike balanced search trees, hashing does not assume existence of key ordering and usually does not preserve it. This makes hashing less suitable for applications that need to iterate over the keys in or-der or require range queries such as counting the number of keys between some lower and upper bounds.
B-Trees
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.