How to Win Coding Competitions: Secrets of Champions
Week 2: Computational complexity. Linear data structures
Lecture 3: Vector
Pavel Krotkov
Saint Petersburg 2016
Operations on vector
Let’s define operations we need for this data structure.
2/9
Operations on vector
Let’s define operations we need for this data structure.
O(1) operations
2/9
Operations on vector
Let’s define operations we need for this data structure.
O(1) operations
I inserting an element to the end of vector
2/9
Operations on vector
Let’s define operations we need for this data structure.
O(1) operations
I inserting an element to the end of vector
I removing an element from the end of vector
2/9
Operations on vector
Let’s define operations we need for this data structure.
O(1) operations
I inserting an element to the end of vector
I removing an element from the end of vector
I accessing an element by its index
2/9
Operations on vector
Let’s define operations we need for this data structure.
O(1) operations
I inserting an element to the end of vector
I removing an element from the end of vector
I accessing an element by its index
All other operations can be performed in linear time.
2/9
Organizing vector in memory
All elements are stored in some array.
I 0-th element of vector corresponds to 0-th element of array
3/9
Organizing vector in memory
All elements are stored in some array.
I 0-th element of vector corresponds to 0-th element of array
I 1-st element of vector corresponds to 1-st element of array
3/9
Organizing vector in memory
All elements are stored in some array.
I 0-th element of vector corresponds to 0-th element of array
I 1-st element of vector corresponds to 1-st element of array
I etc.
3/9
Extra space
Array length will be always equal to some power of 2.
4/9
Extra space
Array length will be always equal to some power of 2.
I we will have some space reserved for new elements.
4/9
Extra space
Array length will be always equal to some power of 2.
I we will have some space reserved for new elements.
Example
I vector of 3 elements
3 6 2
4/9
Extra space
Array length will be always equal to some power of 2.
I we will have some space reserved for new elements.
Example
I vector of 3 elements
3 6 2
I vector of 5 elements
3 6 2 5 8
4/9
Inserting elements
Almost always inserting an element is very simple.
3 6 2 3 6 2 5
5/9
Inserting elements
Almost always inserting an element is very simple.
3 6 2 3 6 2 5
Special case: vector size is equal to array size.
5/9
Inserting elements
Almost always inserting an element is very simple.
3 6 2 3 6 2 5
Special case: vector size is equal to array size.
Let’s allocate array of doubled size, copy all elements and insert new element.
3 6 2 5 3 6 2 5 8
5/9
Complexity analysis
Let’s analyze complexity of insert and access operations.
6/9
Complexity analysis
Let’s analyze complexity of insert and access operations.
I accessing an element always takes O(1) operations
I just accessing corresponding element of array
6/9
Complexity analysis
Let’s analyze complexity of insert and access operations.
I accessing an element always takes O(1) operations
I just accessing corresponding element of array
I removing an element always takes O(1) operations
I just decreasing current size of vector
6/9
Complexity analysis
Let’s analyze complexity of insert and access operations.
I accessing an element always takes O(1) operations
I just accessing corresponding element of array
I removing an element always takes O(1) operations
I just decreasing current size of vector
I inserting an element almost always takes O(1) operations
I just increasing size of vector and assigning value to corresponding element of array
6/9
Complexity analysis
Let’s analyze complexity of insert and access operations.
I accessing an element always takes O(1) operations
I just accessing corresponding element of array
I removing an element always takes O(1) operations
I just decreasing current size of vector
I inserting an element almost always takes O(1) operations
I just increasing size of vector and assigning value to corresponding element of array
I except cases when size of vector is equal to size of array
6/9
Complexity analysis
Let’s analyze complexity of insert and access operations.
I accessing an element always takes O(1) operations
I just accessing corresponding element of array
I removing an element always takes O(1) operations
I just decreasing current size of vector
I inserting an element almost always takes O(1) operations
I just increasing size of vector and assigning value to corresponding element of array
I except cases when size of vector is equal to size of array
I we’ll call such operations long insert operations
6/9
Complexity analysis
Let’s say we performed k insert operations.
7/9
Complexity analysis
Let’s say we performed k insert operations.
I we performed some long insert operations
I for sizes of vector 1, 2, . . . , 2blog2 kc
7/9
Complexity analysis
Let’s say we performed k insert operations.
I we performed some long insert operations
I for sizes of vector 1, 2, . . . , 2blog2 kc
I each long insert takes O(n) operations, where n is current size of vector
7/9
Complexity analysis
Let’s say we performed k insert operations.
I we performed some long insert operations
I for sizes of vector 1, 2, . . . , 2blog2 kc
I each long insert takes O(n) operations, where n is current size of vector
I total time of these insert operations is
O(1 + 2 + . . . + 2blog2 kc ) = O(2 × 2blog2 kc ) = O(k)
7/9
Complexity analysis
Let’s say we performed k insert operations.
I we performed some long insert operations
I for sizes of vector 1, 2, . . . , 2blog2 kc
I each long insert takes O(n) operations, where n is current size of vector
I total time of these insert operations is
O(1 + 2 + . . . + 2blog2 kc ) = O(2 × 2blog2 kc ) = O(k)
I that means that amortized complexity of every insert operation is O(1)
7/9
Removing elements
We have a lot of unused allocated memory in case we did a lot of removes.
8/9
Removing elements
We have a lot of unused allocated memory in case we did a lot of removes.
1
I let’s decrease size of array if we have less then 3 of elements in use
8/9
Removing elements
We have a lot of unused allocated memory in case we did a lot of removes.
1
I let’s decrease size of array if we have less then 3 of elements in use
I it can be proved that even in this case amortized complexity of all operations is
O(1)
8/9
Thank you
for your attention!
9/9
