Big-O Notation

Big-O Complexity Chart 데이터(N)가 늘어날 때 처리 비용이 얼마나 급격히 늘어나는지 보여줍니다. Big-O는 실제 실행 시간이나 정확한 명령 수가 아니라 입력 증가에 따른 성장 경향을 비교합니다.
아래 막대 높이는 개념 비교용이며 특정 N의 실제 연산량을 뜻하지 않습니다.
O(2ⁿ)과 O(n!)은 N이 조금만 커져도 계산이 불가능할 정도로 폭발합니다.

O(1)

O(log n)

O(n)

O(n log n)

O(n²)

O(2ⁿ)

O(n!)

O(1): 상수 시간 (Array Index) 이미 만들어진 배열에서 인덱스로 원소 하나를 접근하는 핵심 연산은 N과 무관하게 1 Step, O(1)입니다. 화면에 배열을 준비하는 과정 자체는 O(n)이지만 측정에서 제외합니다.

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

Comparisons: 0

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

N: 15

Comparisons: 0

Θ(2ⁿ): 지수 시간 (Tower of Hanoi) 하노이의 탑은 원판이 N개일 때 정확히 최소 2^N - 1번 움직이므로 Θ(2ⁿ)입니다. Big-O로도 O(2ⁿ)이라 표기할 수 있습니다.
원판 하나 추가될 때마다 이동 횟수가 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