빅오 치트시트

모든 개발 도구

무료

검색과 인쇄가 가능한 빅오 참고자료입니다: 배열, 해시 테이블, 트리, 힙, 그래프, 정렬, 탐색의 시간 및 공간 복잡도까지. 무료입니다.

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”와 일치하는 항목이 없습니다.

빅오 치트시트 소개

이 빅오 치트시트는 알고리즘 복잡도를 검색 가능한 한 페이지에 담았습니다: 복잡도 클래스 자체부터 시작해, 배열과 동적 배열, 연결 리스트, 스택과 큐, 해시 테이블, 이진 탐색 트리와 균형 트리, 힙, 그래프, 정렬 알고리즘, 탐색 알고리즘, 자주 쓰는 패턴, 그리고 공간 복잡도까지 시간과 공간 비용을 함께 다룹니다.

자료구조를 선택할 때나 면접을 준비할 때 모두 쓸 수 있는 참고자료입니다: 해시 테이블 조회의 평균과 최악의 경우, 균형 트리가 일반 BST보다 나은 이유, 어떤 정렬이 안정적이고 어떤 것이 제자리(in-place) 정렬인지, 투 포인터, 슬라이딩 윈도우, 메모이제이션 패턴의 비용까지 다룹니다.

이 시트는 무료이며 클라이언트 측에서 동작합니다: 검색창으로 실시간으로 행을 필터링하고, 고정된 목차로 섹션을 이동하고, 클릭 한 번으로 항목을 복사하고, 책상용 참고자료로 페이지를 인쇄할 수 있습니다.

빅오 치트시트 사용 방법

시트를 열고 O(1), O(log n), O(n), O(n log n), O(n²)의 기준을 잡기 위해 복잡도 클래스부터 시작하세요.
hash table, quicksort, BFS 같은 자료구조나 알고리즘을 검색해 모든 행을 실시간으로 필터링하세요.
리스트, 맵, 트리 중에서 선택할 때는 자료구조 섹션들을 비교해 보세요.
항목이나 복사 아이콘을 클릭해 클립보드에 복사하세요.
오프라인 복잡도 참고자료로 시트를 인쇄하세요.

자주 묻는 질문

12개 섹션입니다: 복잡도 클래스, 배열과 동적 배열, 연결 리스트, 스택과 큐, 해시 테이블, 이진 탐색과 균형 트리, 힙, 그래프, 정렬 알고리즘, 탐색 알고리즘, 자주 쓰는 패턴, 공간 복잡도입니다.

네. 값이 다른 경우(해시 테이블 조회, quicksort, 불균형 BST)에는 해당 행에 두 값을 모두 표시하므로 데이터가 최악의 조건일 때의 비용을 확인할 수 있습니다.

바로 그 목적으로 만들어졌습니다: 정렬과 탐색 섹션에 자주 쓰는 패턴 섹션까지 더해 면접관이 소리 내어 말해보라고 요구하는 복잡도들을 다룹니다.

네. 공간 비용이 시간 비용과 함께 표시되며, 마지막 섹션에서 재귀 스택 깊이, 제자리 방식과 보조 공간 사용, 그 사이의 일반적인 트레이드오프를 다룹니다.

네, 완전히 무료입니다: 검색과 인쇄가 가능하며 가입 없이 브라우저에서 렌더링됩니다.

빅오 치트시트

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

빅오 치트시트 소개

빅오 치트시트 사용 방법

자주 묻는 질문

빅오 치트시트는 무엇을 다루나요?

평균과 최악의 경우를 함께 보여주나요?

코딩 인터뷰에도 유용한가요?

공간 복잡도도 다루나요?

빅오 참고자료는 무료인가요?

관련 도구

인기 검색어

이 도구 임베드하기