알고리즘의 점근적 표현

알고리즘

어떠한 문제를 해결하기 위해 사용하는 방법 또는 절차/단계

문제1) 3을 3번 더하면?

방법이 2가지로 나올 수 있습니다.

1. $3 + 3 + 3$
2. $3 \times 3$

Q) 지금 뭐하는거지???

A) 하나의 문제에 대한 방법은 여러 가지가 있을 수 있습니다.
알고리즘에서 추구하는 목표 중 하나는 코드가 동작하는 시간을 최소화하는 것입니다.
따라서 목적에 맞는 효율적인 알고리즘을 선택하고 구현하는 것이 중요합니다

문장으로 표현한다면 “이 문제를 나는 ~방법으로 풀이할거야” 이렇게 말할 수 있습니다.
여기서는 2.의 방법을 선택하는 것이 올바른 선택 입니다.
현재는 수학적으로 표현했지만, 쉽게 말하면 연산자가 1개당 시간이 1씩 증가한다고 보시면 됩니다.

알고리즘 분석

알고리즘 분석은 코드의 실행 속도를 수학적으로 평가하는 과정입니다.

입력 크기 n이 커질수록 연산 횟수가 얼마나 증가하는지를 빅오(Big-O) 표기법으로 나타냅니다.

예를 들어:

• $O(b^2)$: 버블 정렬, 선택 정렬, 삽입 정렬
• $O(n \log n)$: 퀵 정렬, 힙 정렬
• $O(\log n)$: 이진 탐색
• $O(n)$: 선형 탐색

입력이 작을 때는 큰 차이가 없어 보이지만, n이 커질수록 O(n^2)과 O(n log n)의 성능 차이는 눈에 띄게 벌어집니다.
아래 그래프에서도 확인할 수 있듯이, 효율적인 알고리즘 선택은 서비스의 성능을 크게 좌우합니다.

따라서 실제 서비스 개발에서는 단순히 "코드가 동작하는가"를 넘어서,
"입력이 많아졌을 때도 얼마나 빠르게 동작하는가"를 고려해야 합니다.

알고리즘 점근적 표기법

알고리즘의 시간 복잡도나 공간 복잡도를 입력 크기 $n$이 충분히 클 때의 성장률로 표현하는 방법이다.

주로 $f(n)$ (실제 알고리즘 수행 시간)과 $g(n)$ (기준 함수, 예: $n, n \log n, n^2$ 등)을 비교한다.

1. Big-O (상한, Upper Bound)

$f(n)∈O(g(n))  ⟺  ∃c>0,∃n0≥0 s.t. ∀n≥n0, f(n)≤c⋅g(n)$

• 정의: $O(g(n))$는 $f(n)$이 $g(n)$보다 빠르게 커지지 않는다는 의미
• 즉, 충분히 큰 $n$에 대해 $f(n)$은 $g(n)$의 일정한 배수 이내에서 억제된다.

2. Big-Ω (하한, Lower Bound)

$f(n)∈Ω(g(n))  ⟺  ∃c>0,∃n0≥0 s.t. ∀n≥n0, f(n)≥c⋅g(n)$

• 정의: $\Omega(g(n))$는 $f(n)$이 $g(n)$보다 느리게 작아지지 않는다는 의미
• 즉, 충분히 큰 $n$에 대해 $f(n)$은 $g(n)$의 일정한 배수 이상이다.

3. Big-Θ (정확한 차수, Tight Bound)

$f(n)∈Θ(g(n))  ⟺  ∃c1>0,∃c2>0,∃n0≥0 s.t. ∀n≥n0, c1⋅g(n)≤f(n)≤c2⋅g(n)$

• 정의: $\Theta(g(n))$는 $f(n)$이 $g(n)$과 동일한 성장률을 가진다는 의미
• 즉, 충분히 큰 $n$에 대해 $f(n)$은 $g(n)$의 일정한 상수 배 위아래로 끼워진다.