|
Polymake Template Library (PTL)
4.2
|
The following brief analysis might help you when choosing the most efficient representation for a concrete case. n is the number of (non-zero in sparse case) elements in the vector.
| Operation | Vector | SparseVector |
|---|---|---|
| sequential iteration | O(n) | O(n), but with greater overhead constant |
| random element access | O(1) | O(log(n)) |
| append an element | O(n) + reallocation costs | O(1) if no preceding random access operations were performed on the sparse vector; O(log(n)) if there already were random access operations on the sparse vector |
1.8.17