Please enable JavaScript.
Coggle requires JavaScript to display documents.
sets, Space and time trade-offs - Coggle Diagram
sets
dictionaries
sets + insert + delete + search
Collection of unordered elements
Universal set or linked lists
Space and time trade-offs
Input enhancement
The idea of pre-process the input at all or in parts and storage the aditional info to acelerate and solve the problem after
Couting sorted methods
Boyer-Moore algorithm for string matching
Worst space efficency to get a better time efficiency
Prestructuring
Explore compensations between space and time utilizing extra space to get the acess more quickly and flexible of the data
Indexing with binary trees
Hashing
A very efficient way to implement dictionaries
Hashing is based on the idea of distributing keys among a one-dimensional array H[0, …, m - 1] called hash table
The key can be an int, char, string
Hash tables must be easy to compute, the 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 and the hash function needs to distribute keys among the cells of the hash table as evenly as possible
Colisions
Approachs
Open hashing
Closed hashing
A phenomenon of two or more keys being hashed into the same cell of the hash table
Dynamic programming
Bottom-up
Top-down
Divide a problem into subproblems