4 ms·
Geometrically-growing arrays (std::vector) and hash tables also have amortized O(1) insertion complexity. They are some of the most widely-used data structures
by lqr 5y ago
Geometrically-growing arrays (std::vector) and hash tables also have amortized O(1) insertion complexity. They are some of the most widely-used data structures of all. I agree that amortized guarantees can be a problem in certain applications, but it seems that programmers are happy to accept them most of the time.
- tsumnia 5y agoTrue, I think it's more that skiplists are both amortized and (taught to) expand randomly unless you dig deeper into optimizing the structure. I think with regard to hash tables, the annoyance of hashing is overlooked due to the simplicity of the algorithm. From a purely academic side, its difficult to explain why you'd use one data structure over another. We can say THIS structure has an O() for THIS operation, but its often at the tradeoff of another operation. Then it comes down to ease of implementation, where I'd say skiplists have a harder time explaining vs. hashing.