21. Order Notation

 알고리즘이 얼마나 빠른지를 어떻게 표현할까? 초 단위로 실행 시간을 재면 안 되냐고 할 수 있는데, 컴퓨터 성능마다 결과가 달라지니까 의미가 없다. 그래서 입력 크기 n이 커질수록 step이 얼마나 늘어나는가를 보는 거다. 자료구조에서 배운 시간 복잡도랑 완전히 같은 개념. 지금까지 배운 이산구조의 앞의 개념과 이어지지 않고 독립된 개념이다.

---

Runtime Function f(n)

 알고리즘의 시간을 입력 크기 n의 함수로 나타낸다. 여기서 중요한 건 worst-case, 즉 최악의 경우를 기준으로 한다는 것. "이 알고리즘은 최대 이만큼 걸린다"는 보장을 하기 위해서다.

 

함수의 종류:

• Constant: f(n) = c
• Logarithmic: f(n) = log n
• Linear: f(n) = an + b
• Quadratic: f(n) = an² + bn + c
• Exponential: f(n) = cⁿ

---

Big-O, Ω, Θ: 핵심 세 가지

Big-O: 상한 (Upper Bound)

f(n) = O(g(n)) ↔ lim f(n)/g(n) < ∞

 

"f(n)은 아무리 많아도 g(n)만큼 자란다."

≤ 에 대응하는 개념.

 

핵심 규칙: 상수 계수랑 낮은 차수는 무시한다. n이 엄청 커지면 어차피 의미가 없어지기 때문이다.

3n + 47       = O(n)    → 상수 47, 계수 3 무시
2¹⁰ · n² + n = O(n²)   → 낮은 차수 n 무시
2ⁿ + n¹⁰⁰   = O(2ⁿ)   → 지수가 다항보다 훨씬 빠르게 자람
135 + 1/n    = O(1)    → 상수

 

주의: 2ⁿ + n¹⁰⁰에서 n¹⁰⁰이 커 보이지만, 지수함수는 다항함수를 압도한다. n = 1000이면 2¹⁰⁰⁰ >> 1000¹⁰⁰.

Big-Ω: 하한 (Lower Bound)

f(n) = Ω(g(n)) ↔ lim f(n)/g(n) > 0

 

"f(n)은 아무리 적어도 g(n)만큼 자란다."

≥ 에 대응하는 개념.

Big-Θ: 상한과 하한이 같을 때 (Tight Bound)

f(n) = Θ(g(n)) ↔ lim f(n)/g(n) = c (0 < c < ∞)

 

"f(n)은 딱 g(n)만큼 자란다."

= 에 대응. O이면서 동시에 Ω인 경우.

f(n) = 3n + 47
→ O(n) ✅, Ω(n) ✅
→ 따라서 Θ(n) ✅

---

little-o, little-ω

Big-O, Ω에서 등호를 제거한 것.

• o: f(n) = o(g(n)) ↔ lim f(n)/g(n) = 0 → g(n)보다 엄격하게 느리게 자람 (< 에 대응)
• ω: f(n) = ω(g(n)) ↔ lim f(n)/g(n) = ∞ → g(n)보다 엄격하게 빠르게 자람 (> 에 대응)

n = O(n²)  ✅  (n² 이하로 자람)
n = o(n²)  ✅  (n²보다 엄격하게 느림)
n² = O(n²) ✅  (n² 이하로 자람)
n² = o(n²) ❌  (같은 속도니까 엄격하게 느리다고 할 수 없음)

---

복잡도 순서

빠름 → 느림 순서:

Θ(1) ≪ Θ(log n) ≪ Θ(n) ≪ Θ(n²) ≪ Θ(2ⁿ)

• log n: 어떤 polynomial보다도 느리게 자람 → binary search가 linear search보다 좋은 이유
• Exponential: 어떤 polynomial보다도 빠르게 자람 → 지수 시간 알고리즘은 사실상 사용 불가

---

정리

표기	대응	의미
O	≤	상한: 아무리 많아도 g(n)
Ω	≥	하한: 아무리 적어도 g(n)
Θ	=	딱 g(n)만큼
o	<	g(n)보다 엄격하게 느림
ω	>	g(n)보다 엄격하게 빠름