Big-O 速查表

所有開發工具

免費

可搜尋、可列印的 Big-O 參考：陣列、雜湊表、樹、堆積、圖、排序與搜尋的時間與空間複雜度。免費。

Complexity classes

O(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

Access 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

Access 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

Stack 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

Insert: 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

BST 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

Peek 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

Adjacency 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

Bubble 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

Linear 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

Two 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

In-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」。

關於 Big-O 速查表

這份 Big-O 速查表把演算法複雜度放在一個可搜尋的頁面：先是複雜度類別本身，接著是陣列與動態陣列、鏈結串列、堆疊與佇列、雜湊表、二元搜尋樹與平衡樹、堆積、圖、排序演算法、搜尋演算法、常見模式，以及空間複雜度說明的時間與空間成本。

無論是選擇資料結構還是準備面試，它都是很好的參考：雜湊表查詢的平均與最壞情況、為何平衡樹勝過普通 BST、哪些排序是穩定的、哪些是原地的，以及雙指標、滑動視窗與備忘錄模式的成本。

此速查表免費且在用戶端執行：用搜尋框即時篩選列、用固定的目錄在各段落間跳轉、一鍵複製任何項目，並可列印頁面作為桌邊參考。

如何使用 Big-O 速查表

開啟速查表，從「複雜度類別」開始，建立 O(1)、O(log n)、O(n)、O(n log n) 與 O(n²) 的概念。
搜尋 hash table、quicksort 或 BFS 等結構或演算法，即時篩選每一列。
在清單、映射與樹之間做選擇時，比較各資料結構段落。
點選項目或其複製圖示，即可將它複製到剪貼簿。
列印速查表，取得離線的複雜度參考。

常見問題

共十二個段落：複雜度類別、陣列與動態陣列、鏈結串列、堆疊與佇列、雜湊表、二元搜尋樹與平衡樹、堆積、圖、排序演算法、搜尋演算法、常見模式，以及空間複雜度說明。

有。在兩者不同的地方（雜湊表查詢、快速排序、不平衡的 BST），該列會同時註明，讓您看到資料不利時的成本。

它正是為此而建：排序與搜尋段落加上常見模式段落，涵蓋面試官要求您口頭說出的複雜度。

涵蓋。空間成本與時間成本並列顯示，最後的段落則涵蓋遞迴堆疊深度、原地與輔助空間，以及一般的取捨。

是的，完全免費：可搜尋、可列印，在瀏覽器中呈現，無需註冊。

Big-O 速查表

Complexity classes

Arrays & dynamic arrays

Linked lists

Stacks & queues

Hash tables

Binary search trees & balanced trees

Heaps

Graphs

Sorting algorithms

Searching algorithms

Common patterns

Space complexity notes

關於 Big-O 速查表

如何使用 Big-O 速查表

常見問題

Big-O 速查表涵蓋哪些內容？

它有顯示平均與最壞情況嗎？

對程式面試有幫助嗎？

它也涵蓋空間複雜度嗎？

Big-O 參考免費嗎？

相關工具

熱門搜尋

嵌入此工具