나는 알고리즘엔 엄청 약하다. 솔직히 아직도 잘 모르겠다.
그래서 이번에 알고리즘 관련 복습을 할 겸, 내 알고리즘이 어느 정도의 효율을 가지고 있는지,
어떻게 측정하는지를 써보려고 한다.
(주의! 이건 필자가 공부한 걸 바탕으로 적어 내려 가는 것이기 때문에 틀릴 수 있음을 미리 경고합니다.)
(주의! 이 글은 C# 언어 기준입니다.)
시간 복잡도 표기법?
보통 알고리즘을 얘기하면 아래의 표기법으로 많이 얘기한다.
각각의 표기법은
빅오: 상한선을 표현
빅오메가: 하한선을 표현
빅세타: 상한선과 하한선 사이를 표현
이렇게 된다.
이걸 현실에 사용한다면 어떻게 표현할 수 있을까?
예를 들어, 누군가와 게임 내에 있는 어떤 기능의 알고리즘의 효율에 대해 이야기한다고 가정해보자.
A: "이 알고리즘은 효율이 어느 정도인가?"
(빅오 기준일 경우)B: "최악의 경우 ($n^2$) 정도의 시간 복잡도를 가집니다."
(빅오메가 기준일 경우)B: "값이 잘 주어질 때 (1) 정도의 시간 복잡도를 가집니다."
(빅세타 기준일 경우)B: "평균적으로 ($\log n$) 시간 복잡도를 가집니다."
개인적인 생각으론 빅오메가는 쓸 일이 없어 보인다.
물론 쓰이긴 할 것이다! 자신의 알고리즘에서 최악의 경우가 너무 나빠서 상사한테 마치 괜찮은 알고리즘인 것 마냥 숨길 때 쓰일 것이다.
내 알고리즘의 시간 복잡도 구하기
필자는 수학을 매우 못한다...
그래서 가장 계산하기 쉬운 기본적인 예시만 들어서 설명하겠다.
일단, 시간 복잡도를 계산할 때 중요한 요소와 규칙이 있다.
중요한 요소
- 조건문 (if)
- 반복문 (for, while, foreach)
- 재귀 호출
규칙
- 시간 복잡도에서 상수값은 무시된다.
- 실제 개발자가 짜 놓은 코드를 수행하는 것은 상수 시간으로 간주한다.
예시
1.
void Function(int n)
{
for (int i = 0; i < n; ++i)
{
// 필요한 코드 수행
}
}이 코드의 시간 복잡도는 O(n)이다.
간단하게, 코드를 n번 반복했기 때문이다.
2.
void Function(int n)
{
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
// 필요한 코드 수행
}
}
}이 코드는 n * n번 수행하기 때문에, 시간 복잡도는 O($n^2$) 이다.
3.
void Function(int n)
{
// 짝수값마다 코드를 수행
for (int i = 0; i < n; i += 2)
{
// 코드 수행
}
}이 코드는 i를 2씩 더해서 $\frac n2$번 코드를 반복하기 때문에, O($\frac n2)$일 것 같지만...!
$\frac n2$은 $\frac {1}{2} n$이기 때문에
시간 복잡도에서는 상수를 무시하므로 그냥 O(n)이다.
4.
void Function(int n)
{
for (int i = 0; i < n; ++i)
{
// 홀수 일 때만 코드를 수행하도록 함
if (n % 0)
{
continue;
}
// 코드 수행
}
}이 코드는 예시 3번과 유사한데, i += 2를 하는 대신 if을 넣어서 짝수 케이스를 무시하도록 하고 있다.
이것은 어떻게 계산할까?
if문은 if조건문 코드와 내부 코드 else if의 조건문, else 내의 코드 등등을 다 더하는 계산을 한다.
그리고 코드 한 줄 한 줄은 앞서 얘기한 대로 상수 실행 값으로 처리한다.
if조건문의 코드 실행 시간을 $c_0$, continue 코드의 실행 시간을 $c_1$, 그 아래 나머지 코드 실행 시간을 $c_2$이라고 하면,
if문의 실행시간을 이것을 다 더한 $(c_0 + c_1 + c_2)$이 되고, 이것을 for 반복문으로 n번 반복하니,
이 코드의 복잡도는 3f(n) = $(c_0 + c_1 + c_2) * n$ 이 된다.
그리고 시간 복잡도를 따질 때, 상수는 무시되므로 이 예시의 시간 복잡도는 O(n)이 된다.
5.
void Function(int n)
{
if (n == 0)
{
return;
}
Function(n / 2);
}여기서부턴 조금 계산이 어려워진다.
재귀 함수가 나올 때 공식의 모습은 함수 공식 안에 함수 공식을 또 호출하는 모양이 나온다.
그래서 위 예시의 함수는, $f(n) = f(\frac {1}{2}n) + c_0$이다. (상수 값 $c_0$는 if문 처리 시간을 뜻한다.)
여기서 $f(\frac {1}{2}n)$는 다시 $f(\frac {1}{2}n) = f(\frac {1}{4}n) + c_0$ 으로 풀어쓸 수 있는데,
이걸 위 첫 공식에 대입 하면 $f(n) = f(\frac {1}{4}n) + c_0 + c_0$이 된다.
그리고 또 여기서 한번더 풀어쓰면 $f(n) = f(\frac {1}{8}n) + c_0 + c_0 + c_0$이 된다.
그럼 만약에 여기서 또 이 함수를 풀어쓰고, 거기서 또 풀어쓰고를 무한히 반복하면?
$f(n) = f(\frac {n}{2^k}) + kc_0$ 와 같은 모습이 나올 것이다.
그런데, 코드 로직의 한계상 $2^k$는 n보다 2배 혹은 2배보다 작은 수가 된다.
예를 들어, n = 3일 경우,
- Function(3 / 2) => 1
- Function(1 / 2) => 0
- 0 == 0 이므로 리턴
이렇게 Function(n / 2)가 총 2번 반복하므로, 우리는 n < $2^k$ ≤ 2n임을 알 수 있다.
여기서 머리가 나쁜 나 같은 사람은 범위 계산엔 쥐약이므로 $2^k$ = 2n인 경우만 따져보자.
$2^k$를 2n으로 치환하면, $f(\frac {n}{2n}) + kc_0$가 되는데, $\frac {n}{2n}$을 계산하면, $f(2) + kc_0$이다.
그럼 남은 것은 $f(2)$와 $kc_0$인데, $f(2)$와 $c_0$는 상수이기 때문에 버려진다.
그럼 남은 것은 k뿐인데, k는 어떻게 구하냐? 우리는 여기서 지수의 로그 변환 공식을 기억해야 한다.
'$2^a = b$는 $a = log_2 b$ 이다.'
이 공식과 아까 $2^k = 2n$을 섞으면, 우리는 k의 값을 알아낼 수 있다.
$2^k = 2n$은 $k = log_2 2n$
그럼 이를 다시 $kc_0$에 넣으면, $f(n) = log_2 2n$이 된다, 여기서 로그의 성질에 의해 진수는 더하기로 분리가 가능하므로,
$f(n) = log_2 2 + log_2 n$ => $f(n) = 1 + log_2 n$이 된다. 헉헉
거의 다 왔다! 여기서 상수인 1을 버리면?
$f(n) = log_2 n$
마지막으로! 여기서 밑인 2를 상용로그로 생략하면?
$f(n) = log n$
드디어 구했다!
이로써 우리는 예제의 시간 복잡도가 $log n$임을 구하게 되었다.
그런데!
우리는 아까 $2^k$ = 2n일 때만 구하였다. $2^k$ < 2n 일 때는 어떻게 할까?
이 경우에도 결과적으로 똑같다. $f(\frac {n}{2^k})$를 $f(\frac {n}{2n})$로 치환해서 상수 값으로 버릴 때,
어쨋꺼나 $2^k$는 n보다 크고 2n보다 작은 수므로, 결국엔 n으로 나눠져 상수 값으로 버려질 값이기 때문이다.
하지만, 실제 실행 횟수는 정확히 $log n$값이 아닌 정수로 딱딱 떨어지는 횟수이므로 빅오로는 표기하기 애매하다.
그래서 이 경우에는 평균 시간 복잡도인 빅세타로 표기해야 한다.
결국, 이 예제의 정확한 시간 복잡도는
Θ(log n)
마무리하며...
나는 솔직히 알고리즘의 시간 복잡도를 써본 적 없다. 아마 앞으로도 평생 쓸 일이 없을 것이라 생각하지만, 한번쯤 복습하는 것도 나쁘지 않다고 생각한다. 왜인지 회사에서는 이런걸 쓰지도 않음에도 꼭 면접 볼 때 이것 관련 지식을 요구하므로...
p.s 오늘 하루 종일 예제 5에 대해 어떻게 계산하는지 구글링을 엄청 했는데,
다들 마스터 정리의 기본 예제인 '$T(n) = 2T(\frac {1}{2}n) + O(n)$은 Θ(n log n)이다.' 만 주구장창 대충 설명하고 있고
왜 그렇게 되는지 하나하나 자세하게 쉽게 설명하는 곳은 없었다.
그래서 이해하느라 애먹었다. :(