%%%%%%%%%%%%%%%%%原文
Data Structure Operations
Data StructureTime ComplexitySpace Complexity
AverageWorstWorst
AccessSearchInsertionDeletionAccessSearchInsertionDeletion
Array
O(1)
O(n)
O(n)
O(n)
O(1)
O(n)
O(n)
O(n)
O(n)
Stack
O(n)
O(n)
O(1)
O(1)
O(n)
O(n)
O(1)
O(1)
O(n)
O(n)
O(n)
O(1)
O(1)
O(n)
O(n)
O(1)
O(1)
O(n)
Doubly-Linked List
O(n)
O(n)
O(1)
O(1)
O(n)
O(n)
O(1)
O(1)
O(n)
Skip List
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(n)
O(n)
O(n)
O(n)
O(n log(n))
Hash Table
-
O(1)
O(1)
O(1)
-
O(n)
O(n)
O(n)
O(n)
Binary Search Tree
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(n)
O(n)
O(n)
O(n)
O(n)
Cartesian Tree
-
O(log(n))
O(log(n))
O(log(n))
-
O(n)
O(n)
O(n)
O(n)
B-Tree
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(n)
Red-Black Tree
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(n)
Splay Tree
-
O(log(n))
O(log(n))
O(log(n))
-
O(log(n))
O(log(n))
O(log(n))
O(n)
AVL Tree
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(n)
Array Sorting Algorithms
AlgorithmTime ComplexitySpace Complexity
BestAverageWorstWorst
Quicksort
O(n log(n))
O(n log(n))
O(n^2)
O(log(n))
Mergesort
O(n log(n))
O(n log(n))
O(n log(n))
O(n)
Timsort
O(n)
O(n log(n))
O(n log(n))
O(n)
Heapsort
O(n log(n))
O(n log(n))
O(n log(n))
O(1)
Bubble Sort
O(n)
O(n^2)
O(n^2)
O(1)
Insertion Sort
O(n)
O(n^2)
O(n^2)
O(1)
Selection Sort
O(n^2)
O(n^2)
O(n^2)
O(1)
Shell Sort
O(n)
O((nlog(n))^2)
O((nlog(n))^2)
O(1)
Bucket Sort
O(n+k)
O(n+k)
O(n^2)
O(n)
Radix Sort
O(nk)
O(nk)
O(nk)
O(n+k)
Graph Operations
Node / Edge ManagementStorageAdd VertexAdd EdgeRemove VertexRemove EdgeQuery
Adjacency list
O(|V|+|E|)
O(1)
O(1)
O(|V| + |E|)
O(|E|)
O(|V|)
Incidence list
O(|V|+|E|)
O(1)
O(1)
O(|E|)
O(|E|)
O(|E|)
Adjacency matrix
O(|V|^2)
O(|V|^2)
O(1)
O(|V|^2)
O(1)
O(1)
Incidence matrix
O(|V| ⋅ |E|)
O(|V| ⋅ |E|)
O(|V| ⋅ |E|)
O(|V| ⋅ |E|)
O(|V| ⋅ |E|)
O(|E|)
Heap Operations
TypeTime Complexity
HeapifyFind MaxExtract MaxIncrease KeyInsertDeleteMerge
Linked List (sorted)
-
O(1)
O(1)
O(n)
O(n)
O(1)
O(m+n)
Linked List (unsorted)
-
O(n)
O(n)
O(1)
O(1)
O(1)
O(1)
Binary Heap
O(n)
O(1)
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(m+n)
Binomial Heap
-
O(1)
O(log(n))
O(log(n))
O(1)
O(log(n))
O(log(n))
Fibonacci Heap
-
O(1)
O(log(n))
O(1)
O(1)
O(log(n))
O(1)