Please enable JavaScript.
Coggle requires JavaScript to display documents.
Sets, Space and Time Trade-Offs - Coggle Diagram
Sets
Important operations
Union
Intersection
Check existence of element
Computer implementation
Bit vector out of an Universe set
Using the list structure to indicate set elements
A data structure that implements the three set basic operations is called a dictionary
Hashing
Hash table
Hash functions
Open hashings
Keys are stored in linked lists attached to a cell
Efficiency depends on the length of the linked list and on the load factor (α)
Operations are of Θ(1) efficiency, on average
Closed hashings
All keys are stored in the hash table itself, no linked lists
Deletion is better done lazily
Double hashing for collision resolution
Average efficiency in Θ(1), worst case in Θ(n)
Design explicitly or implicitly
Space and Time Trade-Offs
Input enhancement
Prestructuring
Dynamic programming