大 O 速查表
可搜索、可打印的大 O 参考——数组、哈希表、树、堆、图、排序和查找的时间和空间复杂度。免费。
Complexity classes
12O(1) — constant
Same cost regardless of input size
O(log n) — logarithmic
Halves the problem each step
O(n) — linear
Touches every element once
O(n log n) — linearithmic
Best possible comparison sort
O(n²) — quadratic
Every pair: nested loops over input
O(n³) — cubic
Triple nesting, e.g. naive matrix multiply
O(2^n) — exponential
Doubles per element: all subsets
O(n!) — factorial
All orderings: brute-force permutations
n = 10^6: O(n log n) ≈ 2×10^7 ops
Fine — well under a second
n = 10^6: O(n²) = 10^12 ops
Too slow — think minutes to hours
Rule: drop constants and lower terms
O(3n² + 5n) is just O(n²)
Amortized O(1)
Occasionally slow, cheap on average
Arrays & dynamic arrays
11Access by index — O(1)
Direct address arithmetic
Search (unsorted) — O(n)
Must scan every element
Search (sorted) — O(log n)
Binary search on sorted data
Append (dynamic) — O(1) amortized
Occasional resize copies all
Insert at front/middle — O(n)
Shifts all later elements
Delete at end — O(1)
No shifting required
Delete at front/middle — O(n)
Shifts elements to close the gap
Resize (grow ×2) — O(n)
Copy into a bigger buffer
Slice/copy — O(k)
Proportional to slice length
Space — O(n)
May hold up to 2× capacity slack
Cache-friendly: contiguous memory
Real-world edge over linked lists
Linked lists
10Access by index — O(n)
Must walk from the head
Search — O(n)
Linear scan, no shortcuts
Insert/delete at head — O(1)
Repoint the head pointer
Insert/delete at tail — O(1) with tail ptr
O(n) without one (singly)
Insert after known node — O(1)
The big win over arrays
Delete known node (doubly) — O(1)
Prev pointer makes unlink cheap
Delete known node (singly) — O(n)
Must find the predecessor
Reverse — O(n) time, O(1) space
Classic pointer-flip interview task
Detect cycle — O(n), O(1) space
Floyd's tortoise and hare
Space — O(n) plus pointer overhead
1–2 pointers per node
Stacks & queues
10Stack push/pop/peek — O(1)
LIFO: last in, first out
Stack search — O(n)
No random access
Queue enqueue/dequeue — O(1)
FIFO: first in, first out
Deque push/pop both ends — O(1)
Double-ended queue
Queue via 2 stacks — O(1) amortized
Classic interview construction
Min-stack — O(1) getMin
Track min alongside each push
Monotonic stack — O(n) total
Next greater element problems
Stack use: DFS, undo, call stack
Recursion is an implicit stack
Queue use: BFS, schedulers, buffers
Level-order processing
Space — O(n)
One slot per stored element
Hash tables
11Insert — O(1) avg, O(n) worst
Worst = all keys collide
Lookup — O(1) avg, O(n) worst
Hash, then probe the bucket
Delete — O(1) avg, O(n) worst
Same story as lookup
Resize/rehash — O(n)
Triggered past the load factor
Load factor ~0.7
Typical resize threshold
Chaining
Collisions become linked lists
Open addressing
Probe for the next free slot
Ordered iteration — not provided
Use a tree map if order matters
Hash set membership — O(1) avg
The go-to de-dupe structure
Space — O(n)
Plus empty buckets overhead
Pattern: trade O(n) space for O(1) lookups
Two-sum in one pass
Binary search trees & balanced trees
12BST search/insert/delete — O(h)
h = tree height
BST average — O(log n)
Random inserts stay bushy
BST worst — O(n)
Sorted inserts make a chain
AVL all ops — O(log n) guaranteed
Strict balance, fast lookups
Red-black all ops — O(log n)
Looser balance, faster writes
B-tree all ops — O(log n)
Wide nodes: databases, disks
In-order traversal — O(n)
Visits keys in sorted order
Min/max — O(log n) balanced
Walk far left / far right
Successor/predecessor — O(log n)
Ordered neighbors of a key
Range query — O(log n + k)
k = number of results
Trie lookup — O(L)
L = key length, not item count
Space — O(n)
2–3 pointers per node
Heaps
10Peek min/max — O(1)
Root holds the extreme
Insert — O(log n)
Bubble up to restore order
Extract min/max — O(log n)
Pop root, sift down
Build heap from array — O(n)
Heapify beats n inserts
Search arbitrary key — O(n)
Heaps are not for lookups
Decrease-key — O(log n)
Core of Dijkstra's algorithm
Top-k of n items — O(n log k)
Keep a size-k heap
Two heaps — O(log n) per insert
Running median pattern
Stored as an array
Children at 2i+1, 2i+2
Space — O(n)
No pointers needed
Graphs
12Adjacency list space — O(V + E)
Best for sparse graphs
Adjacency matrix space — O(V²)
Best for dense graphs
Edge check: list O(deg), matrix O(1)
The core trade-off
Iterate neighbors: list O(deg), matrix O(V)
Lists win for traversal
BFS / DFS — O(V + E)
With an adjacency list
Topological sort — O(V + E)
DAG ordering (Kahn / DFS)
Dijkstra — O((V + E) log V)
Binary heap, no negative edges
Bellman-Ford — O(V·E)
Handles negative edges
Floyd-Warshall — O(V³)
All-pairs shortest paths
Prim / Kruskal MST — O(E log V)
Minimum spanning tree
Union-Find — O(α(n)) ≈ O(1)
With rank + path compression
A* — O(E) best case
Heuristic-guided Dijkstra
Sorting algorithms
13Bubble sort — O(n²), best O(n)
O(1) space; only teaching value
Insertion sort — O(n²), best O(n)
O(1) space; great when nearly sorted
Selection sort — O(n²) always
O(1) space; fewest swaps
Merge sort — O(n log n) always
O(n) space; stable; predictable
Quick sort — avg O(n log n), worst O(n²)
O(log n) space; fastest in practice
Heap sort — O(n log n) always
O(1) space; not stable
Tim sort — O(n log n), best O(n)
Python/Java built-in; stable
Counting sort — O(n + k)
k = value range; not comparison
Radix sort — O(d·(n + k))
d = digits; ints and strings
Bucket sort — avg O(n + k), worst O(n²)
Uniformly distributed input
Shell sort — ~O(n^1.3)
Gap-based insertion sort
Comparison-sort lower bound — Ω(n log n)
Cannot do better by comparing
Stable: merge, insertion, tim, counting
Equal keys keep their order
Searching algorithms
11Linear search — O(n)
Only option for unsorted data
Binary search — O(log n)
Sorted arrays only
Binary search space — O(1) iterative
O(log n) if recursive
Hash lookup — O(1) avg
Fastest membership test
BST search — O(log n) balanced
Also gives sorted neighbors
Trie prefix search — O(L)
Autocomplete workhorse
BFS shortest path (unweighted) — O(V + E)
First hit is the shortest
lower_bound / bisect — O(log n)
First element >= target
Quickselect (k-th element) — avg O(n)
Worst O(n²); no full sort
Ternary search — O(log n)
Peak of a unimodal function
Interpolation search — avg O(log log n)
Uniform sorted data only
Common patterns
12Two pointers — O(n)
Pair sums in a sorted array
Sliding window — O(n)
Best subarray of size/condition k
Fast & slow pointers — O(n)
Cycle detection, list middle
Prefix sums — O(n) build, O(1) query
Range-sum questions
Binary search on answer — O(n log range)
"Min capacity to ship in D days"
Monotonic stack — O(n)
Next greater / histogram area
Backtracking — O(2^n) or O(n!)
Subsets / permutations search
Memoized DP — states × transition cost
Kills exponential recursion
Greedy — usually O(n log n)
Sort, then one linear pass
Divide & conquer — T(n) = 2T(n/2) + O(n)
Master theorem: O(n log n)
Bit manipulation — O(1) per op
Sets of <=64 items in an int
Meet in the middle — O(2^(n/2))
Halves an exponential search
Space complexity notes
11In-place — O(1) extra space
Quick sort, heap sort, reversal
Recursion costs stack space
Depth d means O(d) memory
DFS space — O(h) / O(V) worst
h = depth of recursion
BFS space — O(w)
w = widest level (can be n/2)
Merge sort — O(n) auxiliary
The price of stability
Memoization — O(#states)
Time saved, memory spent
DP table row trick — O(n²) → O(n)
Keep only the previous row
Hash-based de-dupe — O(n) space
vs O(1) sort-first approach
Tail recursion — O(1) if optimized
Not guaranteed in every language
Streaming — O(1) or O(k) space
One pass, constant memory
Always state time AND space
Interviews expect both
没有条目匹配“:q”。
关于 大 O 速查表
这份大 O 速查表将算法复杂度汇集在一个可搜索的页面上：复杂度等级本身，然后是数组和动态数组、链表、栈和队列、哈希表、二叉搜索树和平衡树、堆、图、排序算法、查找算法、常见模式，以及空间复杂度说明的时间和空间开销。
它既是选择数据结构的参考，也适用于面试准备——哈希表查找的平均和最坏情况、为什么平衡树优于普通 BST、哪些排序是稳定的、哪些是原地排序，以及双指针、滑动窗口和记忆化模式的开销。
本速查表免费且在客户端运行：使用搜索框实时过滤行，通过固定目录在章节间跳转，点击即可复制任何条目，还可以打印页面作为桌边参考。
如何使用 大 O 速查表
- 打开速查表，从“复杂度等级”开始，建立 O(1)、O(log n)、O(n)、O(n log n) 和 O(n²) 的概念。
- 搜索数据结构或算法如 hash table、quicksort 或 BFS 以实时过滤每一行。
- 在列表、映射和树之间做选择时比较各数据结构章节。
- 点击条目或其复制图标，复制到剪贴板。
- 打印本速查表获取离线复杂度参考。
常见问题
十二个章节：复杂度等级、数组和动态数组、链表、栈和队列、哈希表、二叉搜索和平衡树、堆、图、排序算法、查找算法、常见模式，以及空间复杂度说明。
是的。在两者不同的情况下——哈希表查找、快速排序、不平衡的 BST——该行会同时标明两者，让你看到数据对抗时的开销。
正是为此而建：排序和查找章节加上常见模式章节涵盖了面试官要求你说出的复杂度。
是的。空间开销与时间开销并列展示，结尾章节涵盖了递归栈深度、原地与辅助空间以及常见的权衡取舍。
是的，完全免费——可搜索、可打印，在浏览器中渲染，无需注册。
热门搜索
大 o 速查表
时间复杂度图表
数据结构复杂度
排序算法复杂度
大 o 记号表
空间复杂度图表
算法复杂度参考手册
需要帮助？
使用此工具时遇到问题？请告诉我们的团队。