[알고리즘 시리즈] 알고리즘 분석 방법 : 시간복잡도와 공간복잡도

---

알고리즘 분석 방법

목차

1. 알고리즘이란 무엇인가

2. 알고리즘을 분석하는 방법

3. 시간복잡도란 무엇인가

4. 시간복잡도를 계산하는 방법

5. Growth of functions

6. 공간복잡도란 무엇인가

7. 좋은 알고리즘이란 무엇인가

---

1. 알고리즘이란 무엇인가

문제를 해결하는 일반적인 방법이다.

 

2. 알고리즘을 분석하는 방법

알고리즘의 효율성은 아래 두 가지 기준으로 판단한다.

• 시간 복잡도 (Time Complexity)
• 공간 복잡도 (Space Complexity)

또한, 입력값이 주어지는 상황을 3가지로 나누어 알고리즘을 분석한다.

• worst-case : 최악의 시간 복잡도를 가지는 입력값이 주어진 경우
• average-case : 평균의 시간 복잡도를 가지는 입력값이 주어진 경우
• best-case : 최상의 시간 복잡도를 가지는 입력값이 주어진 경우

알고리즘을 분석할 때는 주로 worst-case를 기준으로 삼는다.

 

3. 시간복잡도란 무엇인가

시간복잡도란 입력의 수와 실행 횟수 간의 함수 관계를 의미한다. 보통 big-O 표기법을 이용하여  '$O(n)$' 과 같이 나타낸다.

 

4. 시간복잡도를 계산하는 방법

시간복잡도는 Asymptotic Analysis를 적용하여 계산한다. 즉, 해당 알고리즘에 가장 영향이 큰 요소만 고려한다. 예를 들어, 시간 복잡도가 $ n^3 + n^2 + 1 $이면, $n^3$ 항에 대해서만 관심을 가진다.

 

따라서, 알고리즘은 보통 아래의 시간 복잡도 중 하나를 가진다.

$n!$

$2^n$

$n^3$

$n^2$

$nlogn$

$n$

$logn$

$1$

 

5. Growth of functions

시간복잡도를 표현하기 위해서 big-O 뿐만 아니라 Ω, Θ, o, ω 와 같이 다양한 함수들이 있다.

 

1) O(g(n)) : big-O

시간복잡도는 g(n) 이하이다.

worst-case의 경우에도 시간복잡도는 g(n)이다.

 

2) Ω(g(n)) : big-Omega

시간복잡도는 g(n) 이상이다.

best-case의 경우에도 시간복잡도는 g(n)이다.

 

3) Θ(g(n)) : big-theta

시간복잡도는 대략 g(n)이다.

모든 케이스에 대해 시간복잡도는 g(n)이다.

 

4) o(g(n)) : small-o

시간복잡도는 g(n) 미만이다.

worst-case의 경우에도 시간복잡도는 g(n)이다.

 

5) ω(g(n)) : small-Omega

시간복잡도는 g(n) 초과다.

best-case의 경우에도 시간복잡도는 g(n)이다.

 

6. 공간 복잡도란 무엇인가

공간 복잡도란 입력의 수와 차지하는 메모리 공간의 수의 함수 관계를 의미한다.

시간 복잡도와 마찬가지로 계산법과 표기법이 동일하다.

예를 들어, 다음과 같이 n!을 구하는 재귀 함수의 공간 복잡도는

def factorial(n):
    if n == 1:
        return 1
    return n*factorial(n)

n부터 1까지의 콜스택을 필요로 하므로 O(n)의 공간복잡도를 가진다.

 

6. 좋은 알고리즘이란 무엇인가

시간 복잡도와 공간 복잡도를 최소한으로 사용하는 알고리즘이 좋은 알고리즘이다. 하지만, 시간 복잡도와 공간 복잡도는 보통 반비례 관계에 있기 때문에 상황에 따라 최적의 알고리즘은 변경될 수 있다.

---