시간복잡도

title: 초등학생도 이해하는 점근 표기법 sidebar: nav: docs-ko aside: toc: true key: 20251121 tags: [algorithm, big-o, complexity] lang: ko math: true —

점근 표기법, 진짜 쉽게 이해하기

“점근 표기법(asymptotic notation)”이라고 하면 어려워 보이는데
사실 한 줄로 말하면 “함수가 얼마나 빨리 커지는지 비교하는 방법” 이야.

1. 먼저, “성장 속도”부터 느껴보자

숫자 n 이 커질 때, 아래 식들은 이렇게 커져:

n : 1, 2, 3, 4, … → 느리게 커짐
n^2: 1, 4, 9, 16, … → 조금 더 빨리 커짐
2^n: 2, 4, 8, 16, 32, 64, … → 엄청 빨리 커짐

달리기 시합으로 비유하면:

n : 걸어서 가는 사람
n^2 : 자전거 타는 사람
2^n : 스포츠카

처음에는 비슷해 보여도, 멀리 갈수록
스포츠카(2^n)가 압도적으로 앞서간다는 느낌만 기억하면 돼.

2. Big-O, Ω, Θ는 “속도 등급표”

점근 표기법에는 세 가지가 자주 나온다.

O (Big-O)
Ω (Big-Omega)
Θ (Big-Theta)

이 세 가지는
“이 함수의 성장 속도가 어느 정도냐” 를 말해주는 등급표 같은 거야.

예제로 이 함수를 보자.

f(n) = n^3 + n^2 + n - 1

여기서 제일 센(빨리 커지는) 녀석은 n^3 이야.

2-1. Big-O : “이 정도보다 느리거나 같은 속도예요”

“f(n)은 대충 n^3 보다 빨리 크지는 않아요.”

라고 말하고 싶을 때 이렇게 쓴다.

f(n) = O(n^3)

Big-O는 위에서 눌러주는 뚜껑 느낌이야.
“이 함수는 최대 이 정도 속도로 커진다” 라고 생각하면 돼.

2-2. Big-Ω : “이 정도보다 빠르거나 같은 속도예요”

이번에는

“f(n)은 적어도 n 만큼은 빨리 커져요.”

라고 말하고 싶다고 해보자.

f(n) = Ω(n)

Big-Ω는 아래에서 받치는 바닥 느낌이야.
“이 함수는 최소 이 정도 속도로는 커진다” 라고 생각하면 돼.

2-3. Big-Θ : “이 속도랑 거의 똑같이 커져요”

우리 함수 f(n)에서 제일 중요한 건 결국 n^3 이었지?

그래서

“f(n)은 n^3 정도 속도로 커진다.”

라고 말할 때 이렇게 쓴다.

f(n) = Θ(n^3)

위에서 눌러 봐도 n^3,
아래에서 받아 봐도 n^3 이라서
딱 n^3 등급이라고 생각하면 된다.

3. 왜 앞의 숫자(상수)는 무시할까?

예를 들어

9n^3
100n^3
0.5n^3

이 세 개는 전부 성장 속도는 똑같이 n^3 이다.

시속 200km 스포츠카 vs 220km 스포츠카 같은 느낌
사람이나 자전거(n, n^2)랑 비교하면 어차피 둘 다 훨씬 빠름

그래서 점근 표기법에서는 이렇게 쓴다.

9n^3 = O(n^3), 100n^3 = O(n^3)

앞에 붙은 9, 100 같은 상수는 그냥 무시하는 거야.

4. `n^100` 은 `O(2^n)` 일까?

질문:

“n^100 (100제곱) 은 2^n 보다 느리거나 같다고 볼 수 있을까?”

정답은 YES.

n^100 : 아무리 커도 다항식(polynomial)
2^n : 지수 함수(exponential, 한 번 늘 때마다 2배, 2배, 2배…)

멀리 가면 갈수록
“2배씩 늘어나는” 쪽이
“n을 많이 곱한 것”보다 항상 훨씬 더 빨리 커진다.

그래서 이렇게 쓴다.

n^100 = O(2^n)

즉,
“100제곱짜리 사람” vs “스포츠카” 싸움이면
결국 스포츠카(2^n)가 이긴다는 뜻이다.

5. 한 페이지 요약

점근 표기법 = “함수가 얼마나 빨리 커지는지(성장 속도)를 비교하는 말”
Big-O, O(·)
- “이 속도보다 느리거나 같은 속도”
Big-Ω, Ω(·)
- “이 속도보다 빠르거나 같은 속도”
Big-Θ, Θ(·)
- “이 속도랑 거의 똑같은 속도”
앞에 붙은 상수(9, 100 등)는 다 무시한다.
지수 함수 2^n 은 아무리 큰 다항식 n^100 보다도 결국 훨씬 빠르게 커진다.

이 정도만 이해해도 알고리즘 시간 복잡도 볼 때
“아, 이 알고리즘이 얼마나 느린지/빠른지” 감이 잡힐 거야!