알고리즘에 대한 고찰 (시간 복잡도)

모든 프로그래머는 자신의 코드가 효율성을 갖추기 위하여 프로그래밍을 하여야 할 의무가 있습니다.

 

알고리즘이란?

설명에 앞서 1부터 100까지 더하는 프로그램을 구현해 봅시다.

아래와 같이 간단하게 구현할 수 있습니다.

int result = 0;
for (int i = 1; i <= 100; i++)
{
  result += i;
}

이것은 C++ 언어를 사용하여 연산을 수행하는 코드입니다. 이 고급 언어를 컴파일, 링킹과 같은 일련의 과정을 거쳐 컴퓨터가 이해할 수 있는 저급 언어로 변환하고, 결과적으로 1부터 100까지 더할 수 있도록 명령하는 과정을 우리는 알고리즘 이라고 합니다.

In mathematics and computer science, an algorithm is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation.

거창하게 설명할 것 없이 컴퓨터로 하여금 특정 명령을 수행하도록 하는 과정을 의미합니다.

 

효율성이란?

그렇다면 방금 작성했던 코드는 효율적인 방법일까요?

제가 생각하는 정답은 모른다 입니다.

효율적이라는 것은 상대적이라 생각합니다.

누군가는 1부터 100까지 더하는 코드를 아래와 같이 구현할 수 있습니다.

int result = (1 + 100) * 100 / 2;

학교 수학 시간에 배웠던 가우스 법칙입니다.

 

이 코드 역시 효율적이다 정의할 수는 없지만, 분명한 것은 반복문을 사용한 코드보다 시간 복잡도 측면에서 효율적인 코드라는 것입니다.

가독성 측면에서 본다면 누군가는 전자의 코드가 더 효율적이라고 볼 수 있기 때문에 시간 복잡도의 측면에서 효율적이라 표현하였습니다.

PC의 연산 성능이 증가하는 요즘, 일부 개발자들은 성능보다 가독성을 우선으로 하는 경우가 있습니다. 저 역시 어느 정도는 동의하지만 가독성은 유지보수의 영역이고, 성능은 운영시점의 영역이기 때문에 둘 사이의 적절한 타협점을 찾는 것이 중요하다고 생각합니다.

 

알고리즘의 성능 측정

알고리즘은 크게 시간 복잡도와 공간 복잡도를 기반으로 그 알고리즘의 성능을 측정합니다.

가독성은 단순히 감성의 영역일 뿐.

시간 복잡도란 코딩 테스트에 단골로 등장하는 내용으로 얼마나 빠르게 동작하는가? 와 관련된 내용입니다.

반면 공간 복잡도란 얼마나 효율적인 리소스로 알고리즘이 동작되는가? 에 관련된 내용입니다.

A라는 기능을 동작하는데 1Gb의 메모리가 필요한 알고리즘은 10Gb의 메모리가 필요한 알고리즘보다 공간 복잡도 측면에서 효율적이라는 뜻입니다.

연산 장치 성능의 발전으로 최근에는 공간 복잡도보다 시간 복잡도가 상대적으로 중요시되지만 임베디드 환경이나 펌웨어 개발, IoT 영역에서는 여전히 공간 복잡도 역시 무시할 수 없는 내용입니다.

 

시간 복잡도와 빅오(Big-O) 표기법

위에서 설명했던 것처럼 효율적이다 라는 것을 수치화 하기 위해서 우리는 시간 복잡도를 사용하고 이것을 Big-O를 통해 표기합니다.

이것을 빅오 표기법이라 부릅니다.

Big-O 표기법은 알고리즘의 런타임 시점에 알고리즘의 상한선을 정의합니다. 다시 말해 알고리즘이 최대로 소요될 수 있는 시간을 의미하며 해당 알고리즘은 그 상한선을 넘지 않아야 합니다. 예를 들어, 동작 시점에 요소 n의 수에 따라 소요 시간이 선형적으로 증가하면 복잡도는 O(n)이 되고, 입력과 무관하게 동일한 소요 시간의 복잡도는 O(1)이 됩니다.

반복문을 통한 1~100 연산은 O(n)이며 가우스 법칙을 통한 방법은 O(1) 입니다.

아래 표는 일반적으로 사용되는 복잡도 수치와 빅오 표기법입니다. 수학적으로 O(x)의 값이 클 수록 소요되는 시간이 늘어나는 것을 의미합니다.

종류	표기법
Constant	O(1)
Linear	O(n)
Logarithmic	O(log(n))
n-log-n	O(n ∗ log(n))
Quadratic	O(n²)

복잡도가 낮은(빠른) 것은 O(1)이며, 가장 높은(느린) 것은 O(n²)입니다.

O(1) < O(log(n)) < O(n) < O(n * log(n)) < O(n²)

 

이를 그래프로 표현하면 다음과 같습니다.

 

O(1)

이것은 입력 n에 대하여 어떠한 값이 들어오더라도 1회만 실행되는 것을 의미합니다. 다시 말해 알고리즘의 소요 시간은 입력에 대하여 독립적이라는 뜻입니다.

int foo(int n)
{
  return n * (n + 1) * (n + 2);
}

물론 어셈블리 관점에서 n이 0인 것과 n이 INT_MAX 인 경우 연산 차이는 있지만, 반복 관점에서 본다면 차이는 없다.

 

O(n)

이것은 n에 따라 소요 시간이 선형적으로 증가하는 코드를 의미합니다.

대표적으로 아래와 같은 for문이 있습니다.

int foo(int n)
{
  int res = 0;
  for (int i = 1; i <= n; ++i)
    res++;
  return res;
}

int res = 0; 코드와 return res;는 O(1)의 시간을 갖습니다. 반면 for 문과 그 안의 res++ 는, n이 1이라면 1번만 동작되고 종료되지만 n이 1억이라면 foo 함수의 증감연산은 1억번 반복될 것입니다.

소요 시간은 2 + 2 * O(n) 일 수 있으나, 반복 의 관점에서 1 ~ n회가 동작하기 때문에 O(n)으로 표기합니다

 

O(n²)

소요 시간이 가장 큰 알고리즘으로, 이중 for문이 있습니다.

int foo(int n)
{
  int res = 0;
  for (int i = 1; i <= n; ++i)
  {
    for (int j = 1; j <= n; ++j)
      res++;
  }
  return res;
}

1회 for문이 O(n)의 시간 복잡도를 갖기 때문에 당연히 이중 for문은 n의 제곱 복잡도를 갖습니다.

각 라인을 주석을 통해 더 상세히 풀어서 설명하면 아래와 같습니다

int foo(int n)
{
  int sum = 0;                    // ---------------------> c1. N과 무관한 상수 시간 O(1)
  for (int i = 1; i <= n; ++i)    // -----> c2. N에 비례하는 선형 시간 O(n)
    for (int j = 1; j <= i; ++j)  // -> c3. N에 비례하는 선형 시간 O(n)
      sum++;                      // ------------------> c4. N과 무관한 상수 시간 O(1)
  return sum;                     // --------------------> c5. N과 무관한 상수 시간 O(1)
}

c1과 c4, c5는 n과 무관하게 동작하는 코드입니다.

c4 자체(1줄)만 본다면 소요 시간은 O(1)입니다

반면 c2와 c3은 각각 n의 소요 시간을 가지고, 이 것이 중첩되었기 때문에 총 소요되는 시간을 방정식으로 나타내면 다음과 같습니다.

= c1 + c4 + c5 + (n * c2) * (n * c3)
= C + Cn * n²

빅오 표기법은 가장 높은 차수의 시간을 기준으로 표기되므로 해당 알고리즘은 O(n²)으로 표기됩니다.