| Data Structure | Average cases | Worst cases | ||||
|---|---|---|---|---|---|---|
| Insert | Delete | Search | Insert | Delete | Search | |
| Array | N/A | N/A | O(1) | N/A | N/A | O(1) |
| Sorted array | O(n) | O(n) | O(log(n)) | O(n) | O(n) | O(log(n)) |
| Stack/Queue | O(1) | O(1) | O(n) | O(1) | O(1) | O(n) |
| Linked list | O(1) | O(1) | O(n) | O(1) | O(1) | O(n) |
| Doubly linked list | O(1) | O(1) | O(n) | O(1) | O(1) | O(n) |
| Hash table | O(1) | O(1) | O(1) | O(n) | O(n) | O(n) |
| Binary search tree | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | O(n) | O(n) |
| AVL tree | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) |
| Red-Black tree | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) |
Graphs
| Node/edge management | Storage size | Add vertex | Add edge | Remove vertex | Remove edge | Query |
|---|---|---|---|---|---|---|
| Adjacency list | O(|V| + |E|) | O(1) | O(1) | O(|V| + |E|) | O(|E|) | O(|V|) |
| Adjacency matrix | O(|V|²) | O(|V|²) | O(1) | O(|V|²) | O(1) | O(1) |
Sorting algorithms
| Algorithm(applied to array) | Time complexity | Stability | ||
|---|---|---|---|---|
| Best cases | Average cases | Worst cases | ||
| Bubble sort | O(n) | O(n²) | O(n²) | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | No |
| Insertion sort | O(n) | O(n²) | O(n²) | Yes |
| Merge sort | O(n log(n)) | O(n log(n)) | O(n log(n)) | Yes |
| Quick sort | O(n log(n)) | O(n log(n)) | O(n²) | Typical in-place sort is not stable; stable versions exist |
Searching algorithms
| Algorithm | Data structure | Worst case |
|---|---|---|
| Sequential search | Array and linked list | O(n) |
| Binary search | Sorted array and binary search tree | O(log(n)) |
| Depth-first search(DFS) | Graph of |V| vertices and |E| edges | O(|V| + |E|) |
| Breadth-first search(BFS) | Graph of |V| vertices and |E| edges | O(|V| + |E|) |
近期评论