Crate comp_sci
This project consists of articles, data structures, algorithms and solutions to common problems.
Sorting algorithms
| Algorithm | Best case | Average case | Worst case | Auxiliary space |
|---|---|---|---|---|
| Selection sort | O(n2) | O(n2) | O(n2) | O(1) |
| Insertion sort | O(n) | O(n2) | O(n2) | O(1) |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick sort | O(n log n) | O(n log n) | O(n2) | O(log n) |
Data structures
Always choose your data structures carefully. Look below for guidance.
Indexing performance
Indexing is the act of accessing an arbitrary element in the data structure.
This is usually achieved with [] in Rust.
| Data structure | Average case | Worst case |
|---|---|---|
| HeapArray | O(1) | O(1) |
| ArrayList | O(1) | O(1) |
Search performance
Searching is the act of finding an arbitrary element within the data structure.
This is usually achieved with a method such as contains(), get() or similar.
| Data structure | Average case | Worst case |
|---|---|---|
| HeapArray | O(n) | O(n) |
| ArrayList | O(n) | O(n) |
Insertion performance
Insertion is the act of inserting an element at an arbitrary position within the data structure.
This is usually achieved with a method such as insert(), and there is sometimes a push()
for inserting at the end of the data structure given it makes sense.
| Data structure | Best case | Average case | Amortized | Worst case |
|---|---|---|---|---|
| HeapArray[1] | N/A | N/A | N/A | N/A |
| ArrayList[2] | O(1) | O(n) | O(n - index) | O(n) |
[1]: HeapArray is fixed-size thus this function is not available.
[2]: ArrayList's insertion performance depends on the index you add an element to.
Adding to the end of the list is O(1) while adding to the front is O(n), because all the prior elements would have to be moved forward.
Further more, if the capacity of the list is exceeded, it will be O(n) as the entire list has to be reallocated.
Deletion performance
Deletion is the act of removing an element from the data structure. This is usually achieved with
a method such as remove().
| Data structure | Best case | Average case | Amortized | Worst case |
|---|---|---|---|---|
| HeapArray[1] | N/A | N/A | N/A | N/A |
| ArrayList[2] | O(1) | O(n) | O(n - index) | O(n) |
[1]: HeapArray is fixed-size thus this function is not available.
[2]: ArrayList's deletion performance depends on the index you delete an element from. Deleting from the end of the list is O(1) while deleting from the front is O(n), because all the prior elements would have to be moved backward.
Space complexity
Space complexity defines how much memory is necessary to represent the data structure.
| Data structure | Space complexity |
|---|---|
| HeapArray | O(n) |
| ArrayList | O(n) |
Modules
| algorithms | |
| data_structures | |
| programs |
Functions
| binary_search | Finds the position of the key within the given slice. |
| remove_duplicates_by_sorting | Removes duplicate entries from Vec with a complexity of O(n log n + n) I believe (TODO). |
| remove_duplicates_with_dual_pointers | Removes duplicate entries from Vec with a complexity of O(n(n+1)/2). |