알고리즘 성능 분석의 필요성

프로그램의 규모는 시간이 지날수록 방대해지고 있습니다. 즉, 처리해야하는 데이터의 양이 많아진다는 것이지요.

입력하는 데이터의 양이 적은 경우에는 무시해도 크게 상관이 없을 수 있지만 그 양이 많아지면 알고리즘 간의 효율성 차이는 커질 수 밖에 없습니다.

예를 들어볼까요?

위 표에서 알 수 있듯이 입력한 데이터의 개수가 6개 미만일 경우에는 알고리즘 A와 B의 실행 속도 차이가 2배를 넘지 않지만, 입력 개수가 100개라고 가정한다면 실행 속도의 차이는 엄청나게 커집니다.

알고리즘 성능 분석의 조건

위에서 살펴본 것처럼 서로 다른 알고리즘을 비교하려면 반드시 동일한 하드웨어(Hardware)를 사용한 상태에서 알고리즘의 실행 시간을 측정해야 합니다.

그러니까, 알고리즘 A는 일반 개인용 컴퓨터에서 측정하고 알고리즘 B는 수퍼 컴퓨터에서 측정을 한다면 측정 결과는 객관성이 없다는 얘기가 됩니다.

또한, 알고리즘을 측정할 때 사용하는 소프트웨어의 환경도 고려되어야 합니다. C 언어와 같은 컴파일 언어를 사용한 경우는 베이직과 같은 인터프리터 언어를 사용한 경우보다 실행 속도가 빠릅니다.

시간 복잡도와 시간 복잡도 함수

시간 복잡도(Time Complexity)는 알고리즘의 절대적인 실행 시간을 나타내는 것이 아닌 알고리즘을 수행하는 데 연산들이 몇 번 이루어지는 지를 숫자로 표기합니다.

그런데 연산(Operation)의 실행 횟수는 보편적으로 그 값이 변하지 않는 상수(Constant)가 아니라 입력한 데이터의 개수를 나타내는 n에 따라 변하게 됩니다.

연산의 개수를 입력한 데이터의 개수 n의 함수로 나타낸 것을 시간 복잡도 함수라고 말하며, 수식으로는 \(T({ n })\) 이라고 표기합니다.

시간 복잡도 예시

양의 정수 n을 n번 더하는 계산을 진행한다고 가정해봅시다.

\({ n }\times { n }\) 을 계산하는 것과 \({ n }\) 을 \({ n }\) 번 더한 것을 계산하는 등 여러 방법이 있습니다.

/* Case 1 */
sum <- n * n;

/* Case 2 */
sum <- 0
for i <- 1 to n do
    sum <- sum + n;
    
/* Case 3 */
sum <- 0
for i <- 1 to n do
    for j <- 1 to n do
        sum <- sum + 1;

위 3개의 알고리즘의 연산 횟수를 비교해보면 아래와 같이 나타낼 수 있습니다. (간단하게 확인하기 위해 루프 제어 연산은 제외합니다.)

곱셈 연산은 덧셈 연산보다 시간이 더 소요되지만 동일하다고 가정할 경우라도 위 3개의 알고리즘을 비교할 수 있습니다.

하나의 연산이 \({ t }\) 만큼의 시간이 필요하다고 가정한다면 Case 1의 경우는 \({ 2t }\) 만큼의 시간이 필요하고 Case 2의 경우는 \(({ 2n }+1)t\) 만큼의 시간, 마지막으로 Case 3의 경우에는 \(({ 2n }^{ 2 }+1)t\) 만큼의 시간이 필요합니다.

빅오 표기법

빅오 표기법(big-oh notation)이란, 시간 복잡두 함수에서 상대적으로 불필요한 연산을 제거하여 알고리즘의 분석을 조금 더 간편하게 할 목적으로 시간 복잡도를 표기하는 방법입니다.

예를 들어, 위에서 살펴본 Case 2의 반복문을 살펴보면

sum <- 0
/* 이 부분 */
for i <- 1 to n do
    sum <- sum + n;
    
// i <- 1 : 대입 연산 1회
// to : n + 1 번의 비교 연산(루프를 탈출하기 직전의 비교 연산 포함)
// n : n 번의 연산

그러니까 하나의 루프 제어문은 전체적으로 보면 \({ 2n }+2\) 개의 연산을 추가하게 됩니다. 따라서 이전에 정리한 Case 2의 연산 횟수 \({ 2n }+1\) 에 루프 제어문의 연산인 \({ 2n }+2\)을 더하면 결과적으로는 \({ 4n }+3\) 의 연산을 필요로 한다는 것이 됩니다.

하지만 중요한 것은 정확한 연산의 개수가 아니라 알고리즘의 일반적인 증가 추세가 필요합니다. 수식에 포함된 n이 커지게 되면 \({ 2n }+1\) 함수와 \({ 4n }+3\) 함수의 차이는 미미해지고 가장 중요한 포인트인 실행 시간이 \({ n }\) 에 정비례한다는 점입니다.

이를 빅오 표기법을 통해 적용시키면 알고리즘이 \({ n }\) 에 정비례하는 실행 시간을 가진다고 말하는 것이 아닌 알고리즘의 시간 복잡도가 \(O({ n })\) 이라고 합니다. 읽을 때는 “빅오 of n” 이라고 읽습니다. 편하게 “빅오엔” 이라고 읽죠.

빅오 표기법의 수학적 정의와 예시

빅오 표기법의 수학적 정의에 대해서 알아봅시다.

수학적 정의, 두 개의 함수 \(f({ n })\) 과 \(g({n})\) 이 주어졌을 때, 모든 \(n\ge { n }_{ 0 }\) 에 대하여 \(|f(n)|\le c|g(n)|\) 을 만족하는 2개의 상수 \({ c }\) 와 \({ n }_{ 0 }\) 가 존재하면 \(f(n)=O(g(n))\) 이다.

\(f({ n })=5\) 이면 \(O(n)\) 이다. \({ n }_{ 0 }=1, { c }=10\) 일 때, \(n\ge1\) 에 대하여 \(5\le10\cdot1\) 이 되기 때문이다.

\(f({ n })=2{ n }+1\) 이면 \(O(n)\) 이다. \({ n }_{ 0 }=2, { c }=3\) 일 때, \(n\ge2\) 에 대하여 \(2{ n }+1\le3{ n }\) 이 되기 때문이다.

\(f({n})=3{ n }^{ 2 }+100\) 이면 \(O({ n }^{ 2 })\) 이다. \({ n }_{ 0 }=100, { c }=5\) 일 때 \(n\ge100\) 에 대하여 \({ 3n }^{ 2 }+100\le{ 5n }^{ 2 }\) 이 되기 때문이다.

많이 쓰이는 빅 표기법은 아래와 같습니다.

최선, 평균, 최악의 경우

동일한 알고리즘도 입력되는 데이터에 따라 다른 실행 시간을 보일 수 있습니다.

예를 들어, 정렬을 하는 알고리즘에 대부분 정렬이 완료되어 있는 데이터를 입력한다면 뒤죽박죽 섞여있는 데이터 집합보다 더 빨리 정렬이 완료될 것입니다.

그래서 알고리즘의 효율성은 입력되는 데이터의 집합에 따라 3가지의 경우로 나누어 평가할 수 있습니다.
최선의 경우(Best Case) : 실행 시간이 가장 적은 경우를 말합니다.
평균적인 경우(Average Case) : 모든 입력을 고려하고 각 입력이 발생하는 확률을 고려한 평균 수행 시간을 말합니다.
최악의 경우(Worst case) : 알고리즘의 수행 시간이 가장 오래 걸리는 경우를 말합니다.

평균적인 경우의 실행 시간이 가장 좋아보이지만 광범위한 데이터 집합에 대하여 알고리즘을 적용시켜 평균 값을 계산하는 것은 매우 어려울 수도 있습니다. 따라서 시간 복잡도의 척도를 계산할 때는 최악의 경우를 주로 사용합니다.

예를 들어서 정렬되지 않은 배열을 순차적으로 탐색하여 특정한 값을 찾는 경우를 생각해봅시다. (이러한 알고리즘을 순차 탐색이라고 합니다.) 기본 연산은 비교 연산이라고 가정한다면,

int sequencialSearch(int list[], int n, int key)
{
    int i;
    for(i = 0; i < n; i++)
    {
        if(list[i] == key)
        {
            return i; // 탐색에 성공하면 키 값의 인덱스 반환
        }
    }
    return -1; // 탐색에 실패하면 -1 반환
}

여기서의 최선의 경우는 찾으려는 값이 배열의 가장 처음에 있는 경우가 됩니다.

반대로, 최악의 경우는 찾으려는 값이 배열의 가장 마지막에 있는 경우가 됩니다. 각각을 빅오 표기법으로 나타내면 \(O(1)\) 과 \(O({ n })\) 이 됩니다.

공간 복잡도

공간 복잡도(Space Complexity)란, 프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양을 말합니다.

총 공간 요구 = 고정 공간 요구 + 가변 공간 요구로 나타낼 수 있으며 수식으로는 \(S(P)=c+S_P(n)\) 으로 표기합니다.

여기서 고정 공간은 입력과 출력의 횟수나 크기와 관계없는 공간의 요구(코드 저장 공간, 단순 변수, 고정 크기의 구조 변수, 상수)를 말합니다.

가변 공간은 해결하려는 문제의 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들을 위해서 필요로 하는 공간, 함수가 순환 호출을 할 경우 요구되는 추가 공간, 그러니까 동적으로 필요한 공간을 말합니다.

공간 복잡도 예시

아래의 코드를 통해 공간 복잡도의 예시를 살펴봅시다.

int factorial(int n)
{
    if(n > 1) return n * factorial(n - 1);
    else return 1;
}

위 코드의 공간 복잡도가 어떻게 될까요? n이 1 이하일 때까지 함수가 재귀적으로 호출되므로 스택에는 n부터 1까지 모두 쌓이게 될겁니다. 즉 공간 복잡도는 \(O(n)\) 이 됩니다.

아래와 같이 구현하게 되는 경우는 어떻게 될까요?

int factorial(int n)
{
    int i = 0;
    int fac = 1;
    for(i = 1; i <= n; i++)
    {
        fac = fac * i;
    }
    return fac;
}

n의 값에 상관없이 스택에는 n과 i 그리고 fac 변수만 저장됩니다. 여기서의 공간 복잡도는 \(O(1)\) 입니다.

Time Complexity vs Space Complexity

시간 복잡도는 “얼마나 빠르게 실행되느냐” 그리고 공간 복잡도는 “얼마나 많은 자원이 필요한가?”
정리해보자면, 좋은 알고리즘이란, “시간도 적게 걸리고 자원의 사용도 적어야 하는 것”

하지만, 시간과 공간은 반비례적인 경향이 있기 때문에 알고리즘의 척도는 시간 복잡도를 위주로 판단합니다.
그러니까 시간 복잡도만 괜찮다면 공간 복잡도는 어느 정도 이해를 해준다는 것! 특히나 요즘과 같은 대용량 시대에는!