常见算法复杂度Cheatsheet

大O符号

大O符号(Big-O notation)是用于描述函数渐近行为的数学符号。它用另一个(通常更简单的)函数来描述一个函数数量级的渐近上界。下图展示了算法分析中一些常见的增长曲线。

fig

数组排序

Algorithm Categories Stability Time Complexity Space Complexity
Best Average Worst Worst
Quicksort Exchange sorts unstable Ω(n log(n)) Θ(n log(n)) O(n^2) O(n) / O(log(n))
Mergesort Merge sorts stable Ω(n log(n)) Θ(n log(n)) O(n log(n)) O(n)
Timsort Hybrid sorts stable Ω(n) Θ(n log(n)) O(n log(n)) O(n)
Heapsort Selection sorts unstable Ω(n log(n)) Θ(n log(n)) O(n log(n)) O(1)
Bubble Sort Exchange sorts stable Ω(n) Θ(n^2) O(n^2) O(1)
Insertion Sort Insertion sorts stable Ω(n) Θ(n^2) O(n^2) O(1)
Selection Sort Selection sorts unstable Ω(n^2) Θ(n^2) O(n^2) O(1)
Shell Sort Insertion sorts unstable Ω(n log(n)) Θ(n(log(n))^2) O(n(log(n))^2) O(1)
Bucket Sort Distribution sorts stable Ω(n+k) Θ(n+k) O(n^2) O(nk) / O(n)
Radix Sort Distribution sorts stable Ω(nk) Θ(nk) O(nk) O(n+k)
Counting Sort Distribution sorts stable Ω(n+k) Θ(n+k) O(n+k) O(k)
Cubesort - stable Ω(n) Θ(n log(n)) O(n log(n)) O(n)

数据结构操作

通用数据结构

Data Structure Time Complexity Space Complexity
Average Worst Worst
Access Search Insertion Deletion Access Search Insertion Deletion
Array Θ(1) Θ(n) Θ(n) / O(1) Θ(n) / O(1) O(1) O(n) O(n) / O(1) O(n) / O(1) O(n)
Stack Θ(n) Θ(n) Θ(1) Θ(1) O(n) O(n) O(1) O(1) O(n)
Queue Θ(n) Θ(n) Θ(1) Θ(1) O(n) O(n) O(1) O(1) O(n)
Singly-Linked List Θ(n) Θ(n) Θ(1) Θ(1) O(n) O(n) O(1) O(1) O(n)
Doubly-Linked List Θ(n) Θ(n) Θ(1) Θ(1) O(n) O(n) O(1) O(1) O(n)
Skip List Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n) O(n) O(n) O(n) O(n log(n))
Hash Table N/A Θ(1) Θ(1) Θ(1) N/A O(n) O(n) O(n) O(n)
Binary Search Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n) O(n) O(n) O(n) O(n)
Cartesian Tree N/A Θ(log(n)) Θ(log(n)) Θ(log(n)) N/A O(n) O(n) O(n) O(n)
B-Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)
Red-Black Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)
Splay Tree N/A Θ(log(n)) Θ(log(n)) Θ(log(n)) N/A O(log(n)) O(log(n)) O(log(n)) O(n)
AVL Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)
KD Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n) O(n) O(n) O(n) O(n)

Heaps Time Complexity
Heapify Find Max Extract Max Increase Key Insert Delete Merge
Sorted LinkedList - O(1) O(1) O(n) O(n) O(1) O(m+n)
Unsorted Linked List - 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(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n))
Fibonacci Heap - O(1) O(log(n)) O(1) O(1) O(log(n)) O(1)

Node / Edge Management Storage Add Vertex Add Edge Remove V ertex Remove Edge Query
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|)

查找算法

Algorithm Data Structure Time Complexity Space Complexity
Average Worst Worst
Depth First Search Graph of |V|vertices and |E|edges - O(|E| + |V|) O(|V|)
Breadth First Search Graph of |V|vertices and |E|edges - O(|E| + |V|) O(|V|)
Binary Search Sorted array of nelements O(log(n)) O(log(n)) O(1)
Brute Force Array O(n) O(n) O(1)
Shortest path by Bellman-Ford Graph with |V|vertices and |E|edges O(|V||E|) O(|V||E|) O(|V|)

REFERENCE

http://www.bigocheatsheet.com/
http://en.wikipedia.org/wiki/Array_data_structure
http://en.wikipedia.org/wiki/Singly_linked_list#Singly_linked_lists
http://en.wikipedia.org/wiki/Doubly_linked_list
http://en.wikipedia.org/wiki/Skip_list
http://en.wikipedia.org/wiki/Hash_table
http://en.wikipedia.org/wiki/Binary_search_tree
http://en.wikipedia.org/wiki/Quicksort
http://en.wikipedia.org/wiki/Merge_sort
http://en.wikipedia.org/wiki/Timsort
http://en.wikipedia.org/wiki/Heapsort
http://en.wikipedia.org/wiki/Bubble_sort
http://en.wikipedia.org/wiki/Insertion_sort
http://en.wikipedia.org/wiki/Selection_sort
http://en.wikipedia.org/wiki/Bucket_sort
http://en.wikipedia.org/wiki/Radix_sort
http://en.wikipedia.org/wiki/Adjacency_list
http://en.wikipedia.org/wiki/Incidence_list
http://en.wikipedia.org/wiki/Incidence_matrix
http://en.wikipedia.org/wiki/Adjacency_matrix
http://en.wikipedia.org/wiki/Linked_list
http://en.wikipedia.org/wiki/Binary_heap
http://en.wikipedia.org/wiki/Binomial_heap
http://en.wikipedia.org/wiki/Fibonacci_heap