Big-O Notation

Big-O Complexity Chart 데이터(N)가 늘어날 때 처리 비용이 얼마나 급격히 늘어나는지 보여줍니다.
O(2ⁿ)과 O(n!)은 N이 조금만 커져도 계산이 불가능할 정도로 폭발합니다.

O(1)

O(log n)

O(n)

O(n log n)

O(n²)

O(2ⁿ)

O(1): 상수 시간 (Array Index) 인덱스로 접근합니다. N=10이든 N=100이든 즉시(1 Step) 찾습니다.

N: 50

Steps: 0

O(log n): 로그 시간 (Binary Search) 범위를 반씩 줄여나갑니다. N=100일 때 고작 7번 이내로 찾습니다.

N: 100

Steps: 0

O(n): 선형 시간 (Linear Search) 처음부터 끝까지 찾습니다. N에 비례해서 시간이 걸립니다.

N: 50

Steps: 0

O(n log n): 선형 로그 시간 (Merge Sort) 반으로 쪼개고(log n) 다시 합치는(n) 과정입니다. 가장 효율적인 정렬 방식입니다.

N: 40

Ops: 0

O(n²): 이차 시간 (Bubble Sort) 이중 루프입니다. 막대끼리 비교하는 횟수가 폭발적으로 많아집니다.

N: 15

Comparisons: 0

O(2ⁿ): 지수 시간 (Tower of Hanoi) 하노이의 탑은 원판이 N개일 때 최소 2^N - 1번 움직여야 합니다.
원판 하나 추가될 때마다 이동 횟수가 2배로 폭증하는 것을 직접 느껴보세요.
(N=3 → 7회, N=4 → 15회, N=5 → 31회...)

Disks (N): Max 8 3

Moves: 0

O(n!): 팩토리얼 시간 (Permutations) 모든 순서의 경우의 수입니다. N=10이면 360만 번 연산해야 합니다.

N (Max 7): 4

Count: 0