개발하는 피자 양목장

나는 알고리즘엔 엄청 약하다. 솔직히 아직도 잘 모르겠다.

그래서 이번에 알고리즘 관련 복습을 할 겸, 내 알고리즘이 어느 정도의 효율을 가지고 있는지,

어떻게 측정하는지를 써보려고 한다.

(주의! 이건 필자가 공부한 걸 바탕으로 적어 내려 가는 것이기 때문에 틀릴 수 있음을 미리 경고합니다.)

(주의! 이 글은 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일 경우,

1. Function(3 / 2) => 1
2. Function(1 / 2) => 0
3. 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)이다.' 만 주구장창 대충 설명하고 있고

왜 그렇게 되는지 하나하나 자세하게 쉽게 설명하는 곳은 없었다.

그래서 이해하느라 애먹었다. :(