시간 복잡도 완벽 이해하기

1. 알고리즘의 효율성 표현

알고리즘의 효율성은 수행 시간 (시간 복잡도) 또는 알고리즘이 수행하는 동안 사용되는 메모리 크기 (공간 복잡도) 로 나타낼 수 있다. 시간 복잡도는 알고리즘이 수행하는 기본적인 연산 횟수를 입력 크기에 대한 함수로 표현한다. 만약, n장의 카드 중에서 최대 숫자를 찾아야 한다면, (n-1) 번 비교를 해야 한다. 입력 크기 n이 커질수록, 연산 횟수는 더 많아질 것이다. 그래서 시간 복잡도는 "입력 크기 n에 따라, 연산 횟수가 얼마나 늘어나는지"를 보여주는 것이다. 함수 형태로 보면 f(n)=n−1이고, 이걸 우리는 입력 크기 n에 대한 함수 표현이라고 말한다. 따라서 시간복잡도는 (n-1) 가 된다. 

 

알고리즘의 복잡도를 표현하는 방법에는 "최악 경우 분석", "평균 경우 분석". "최선 경우 분석" 이 있다. 최악 경우 분석은 ‘어떤 입력이 주어지더라도 얼마 이상을 넘지 않는다’라는 표현이다. 평균 경우 분석은 입력의 확률 분포를 가정하여 분석하는데, 대부분의 경우 균등 분포(uniform distribution)를 가정한다. 즉, 입력이 랜덤하게 들어온다고 가정하고 계산을 한다. 최선 경우 분석은 겨의 사용되지 않는다. 

 

2. 복잡도의 점근적 표기

위의 예시 f(n)=n−1 처럼 시간 또는 공간 복잡도는 입력 크기에 대한 함수로 표기된다. 점근적 표기 (asymptotic notation) 는 입력 크기 n이 매우 커질 때, 알고리즘의 성능이 어떻게 증가하는지 표현하는 방법이다. 이때 다항식의 최고차항만을 계수 없이 취하여 단순한 함수로 근사해 알고리즘의 성능을 비교하기 쉽게 만들어준다. 

 

점근적 표기법에는 3가지 종류가 있다.

 

1️⃣ O(Big-Oh) 

Big-O 표기는 복잡도의 점근적 상한을 나타낸다. 입력 크기 n이 무한히 커질 때, 함수 f(n)이 어떤 단순한 함수 g(n)보다 더 빨리 커지지 않으면, \(f(n) = O(g(n))\) 라고 표현한다. 

 

<계산방법>

 

$$f(n)=2n^2-8n+3$$

1) 최고차항만 남기고 계수를 버린다. \(g(n)=n^2\)

2) 적당한 c 값을 넣고, 이 부등식이 성립하는 최소 $n_0$ 을 찾는다. 

3) 성립한다면 Big-O로 표현 가능

 

 

f(n)을 g(n)보다 항상 작게 만들 수 있는, 즉 \(f(n) ≤ c·g(n)\) 을 만족시키는 상수 c와 n₀가 존재하는지 확인하는 과정에 대해 더 자세히 알아보자. 모든 입력 크기 n에 대해 f(n)이 g(n)을 항상 넘지 않는다는 보장이 필요하다. n이 충분히 크면 f(n) 이 g(n) 보다 항상 작거나 같아야 g(n) 을 f(n) 의 상한이라고 말할 수 있다. 

 

❓어차피 빅오(Big-O)에서는 계수는 무시하고 최고차항만 남긴다고 배웠고, 그러면   \(f(n)=2n^2-8n+3\) 은 당연히  \(O(n^2)\) 아닌가? 왜 굳이 c와 n₀ 같은 수학적 조건까지 붙여야 하는가?

 

👉 "최고차항만 본다”는 직관은 정의의 결과이지, 정의 자체가 아니다. 계수를 무시하는 건 표현상의 편의일 뿐, 실제 정의는 여전히 c가 존재해야 Big-O 성립한다. 

 

<c 찾기>

부등식을 정리하면, \(2n^2-8n+3 ≤ cn^2\)  ⇒ $(2 - c)n^2 - 8n + 3 \le 0$ 이다. 

 

 

상수 \( c = 5 \)를 선택했다 치면, $-3n^2 - 8n + 3 \le 0$ 이다. 

 

❓상수 \( c \)는 어떻게 선정할까?

👉 핵심은 \( f(n) \)이 \( g(n) \)보다 항상 작거나 같게 되는 상한선을 찾는 것이다.  
이를 위해 \( \frac{f(n)}{g(n)} \)의 값을 생각해 보면, 이 비율이 어떤 값을 넘지 않게 되는 최댓값보다 약간 더 큰 수를 \( c \)로 선택하면 된다.

\[
\lim_{n \to \infty} \frac{f(n)}{g(n)} = 2
\]

\( f(n) \)은 결국 \( 2n^2 \)에 가까워진다.  그러므로  \( c = 5 \)일 필요는 전혀 없다. \( c = 2.1 \), \( c = 3 \), \( c = 5 \) 등 2보다 큰 어떤 수를 선택해도 \( n \)이 충분히 크면 \( f(n) \le c \cdot g(n) \) 이 성립한다. 단, 그에 따라 \( n_0 \)는 더 커져야 할 수도 있다.  Big-O는 "존재한다(exists)"는 사실만 중요하고, 가장 작은 \( c \)를 찾는 건 Big-O의 목적이 아니다. 

 

 

<$n_0$ 찾기>

$n_0$은 Big-O 부등식 \( f(n) \le c \cdot g(n) \)이 처음으로 항상 성립하게 되는 최소한의 값이다.  Big-O 표기에서 “모든 \( n \ge n_0 \)”일 때 부등식이 성립함을 보장하는 기준선 역할을 한다.

 

이제 이 부등식이 언제부터 항상 성립하는지를 확인해야 한다. $-3n^2-8n+3 \le 0$ 을 풀면 \( n_0 \le \frac{1}{3} \) 에서 항상 참이다.

 

<결론>
즉, \( c = 5 \), \( n_0 = \frac{1}{3} \)를 선택하면 $f(n) \le c \cdot g(n) \quad \text{for all } n \ge n_0$ 이 성립한다. 1/3 이후에는 n 이 무한대로 증가할 때,  f(n) 은 g(n) 보다 절대로 커질 수 없다. 따라서 \(\mathcal{O}(n^2) \) 이 $f(n)$ 의 점근적 상한이 되는 것이다. 

 

<주의>

그러나 \( f(n) \ne O(\log n),\ f(n) \ne O(n),\ f(n) \ne O(n \log n) \)이다. 각각에 어떠한 c를 선택하더라고 f(n) 보다 크게 만들 수 없기 때문이다. 반면에 \( f(n) = O(n^3) \), \( f(n) = O(2^n) \)은 가능하다.  \( c n^3 > 2n^2 - 8n + 3 \), \( c 2^n > 2n^2 - 8n + 3 \)과 같은 관계가 \( n \)이 무한대로 증가함에 따라 항상 성립하기 때문이다. 다만 Big-O 표기의 정의를 만족하면서 차수가 가장 낮은 함수를 g(n) 으로 선택하는 것이 원칙이다. 

 

2️⃣ Ω(Big-Omega) 

Big-Omega 표기는 복잡도의 점근적 하한을 의미한다.  입력 크기 \( n \)이 무한히 커질 때, 함수 \( f(n) \)이 어떤 단순한 함수 \( g(n) \)보다 더 느리게 커지지 않으면,  \( f(n) = \Omega(g(n)) \) 라고 표현한다.

 

\( f(n) = 2n^2 - 8n + 3 \)의 \(\Omega\)-표기는 \( \Omega(n^2) \)이다.  ‘\( n \)이 증가함에 따라 \( 2n^2 - 8n + 3 \)이 \( c n^2 \)보다 작을 수 없다’라는 의미이다.  
이때 상수 \( c = 1 \)로 놓으면 된다. \(\Omega\)-표기도 복잡도 다항식의 최고차항만 계수 없이 취하면 된다.

 

그러나 \( f(n) \ne \Omega(n^3) \), \( f(n) \ne \Omega(2^n) \)이다. 각각에 어떠한 \( c \)를 선택하더라도 \( f(n) \)보다 작게 만들 수 없기 때문이다.

반면에 \( f(n) = \Omega(\log n) \), \( f(n) = \Omega(n) \), \( f(n) = \Omega(n \log n) \)은 가능하다.  
n이 무한대로 증가할 때, \( c \log n < 2n^2 - 8n + 3 \), \( c n < 2n^2 - 8n + 3 \), \( c n \log n < 2n^2 - 8n + 3 \)과 같은 관계가  성립하는 c가 존재하기 때문이다. 

 

3️⃣ Θ(Theta)

\(\Theta\)-표기는 복잡도의 \( O \)-표기와 \(\Omega\)-표기가 같은 경우에 사용한다.  
따라서 \( f(n) = 2n^2 - 8n + 3 = O(n^2) \), \( f(n) = 2n^2 - 8n + 3 = \Omega(n^2) \)이므로,  
\( f(n) = \Theta(n^2) \)이다.  

3. 연습문제

O(n) 에서 밑에 2개의 예시는 g(n) 을 부풀려서 작성한 예이다. g(n)=n 이 상식적이지만 g(n)=$n^2$ 도 이론적으로 가능은 하다.