알고리즘 성능 평가 [1] : 시간 복잡도(Time Complexity)

 

 

 

 

 

알고리즘의 성능을 판단하는 데에는 시간 복잡도(Time Complexity), 공간 복잡도(Space Complexity) 등이 쓰입니다.

시간 복잡도는 알고리즘이 얼마나 빠르게 실행되는지,

공간 복잡도는 알고리즘이 얼마나 메모리를 잡아먹는지를 판단하는데 쓰입니다.

이번 편에서는 그 중에서도 시간 복잡도(Time Complexity)를 알아보겠습니다.

 

 

 

시간 복잡도 (Time Complexity)

시간 복잡도는 입력되는 데이터의 양에 따라

알고리즘의 수행 시간이나 연산 횟수가 어떻게 달라지는지를 분석하는데 쓰입니다.

 

알고리즘을 짤 때에는 문제를 해결하는 것도 좋지만,

알고리즘을 얼마나 효율적으로 짜는 것 역시 중요합니다.

같은 입력을 넣었을 때, 같은 출력을 갖는다 하더라도, 알고리즘에 따라 성능이 달라질 수 있습니다.

시간 복잡도는 이러한 성능의 부분 중 시간, 즉 연산횟수를 고려할 때 쓰는 개념입니다.

 

 

 

표기법

복잡도는 최악의 경우, 평균의 경우, 최악의 경우. 총 세 가지로 나타낼 수 있습니다.

최악의 경우 : Big-O(빅 오),

평균의 경우 : Big-θ(빅 세타),

최선의 경우 : Big-Ω(빅 오메가)로 나타냅니다.

보통 알고리즘의 성능을 이야기 할 때는 최악의 경우를 생각하여 Big-O(빅 오) 표기법으로 나타냅니다.

 

최선의 경우, 평균의 경우를 고려해 알고리즘을 짰다가,

최악의 경우에 대비를 하는 것 보다는, 처음부터 최악의 경우를 고려해 알고리즘을 설계하는 것이

더 바람직한 방법이기 때문입니다.

 

 

 

알고리즘 성능

출저 - 위키피디아 (https://en.wikipedia.org/wiki/Time_complexity)

 

 

시간복잡도의 여러 유형 중 몇 가지를 알아보겠습니다.

 

 

 

O(1)

 

O(1)은 자료량의 크기가 얼마나 되던간에,

고정 횟수의 연산을 진행합니다.

 

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        System.out.println(arr[0]);
    }
}

배열의 특정 인덱스에 접근해 print 하는 프로그램은,

배열의 크기가 얼마가 되었건 인덱스로 접근하므로 늘 고정된 연산 횟수를 가집니다.

 

 

 

O(n)

 

O(n)은 자료량에 따라 시간이 정비례로 증가합니다.

 

int[] arr = {1, 2, 3, 4, 5};

int sum = 0;

for (int i = 0; i < arr.length; i++) {
    sum += arr[i];
}

 

위 코드와 같이, 배열 내 원소의 값을 하나씩 더해 배열 내 원소의 합을 구하는 프로그램을 작성하였습니다.

이 경우, arr 배열의 원소 하나가 더 생길 때 마다 for문의 연산횟수는 1 증가합니다.

 

 

int[] arr = {1, 2, 3, 4, 5};

int sum = 0;

for (int i = 0; i < arr.length; i++) {
    sum += arr[i];
}

for (int i = 0; i < arr.length; i++) {
    sum += arr[i];
}

 

 

그렇다면, 위 코드와 같이 2개의 for문을 가졌을 경우,

원소 내 값이 1 증가할 때 마다 연산횟수는 2만큼 증가합니다.

이 경우 시간복잡도는 O(2n)일까요? 틀린 표현은 아닙니다.

다만, 연산횟수 자체는 arr의 크기에 비례하며, 빅 오 표기법에서 상수는 크게 중요하지 않습니다.

중요한 것은 입력데이터량에 따른 시간과 연산횟수의 변화입니다.

 

입력 데이터가 작은 경우, 이러한 상수 요소는 꽤 큰 차이를 나타낼 수 있지만,

데이터의 양이 커질수록 상수 요소의 영향은 상대적으로 작아집니다.

 

따라서 O(2n)이라더라도 보통 O(n)으로 나타내곤 합니다.

2, 3번의 고정 연산횟수를 가진 경우도 O(2), O(3) 이 아닌 O(1)으로 나타내는 이유입니다.

 

 

 

O(n^2) / O(n^k) - 거듭제곱

 

 

 

O(n^2)는 데이터의 양이 증가함에 따라, 그 제곱의 비율만큼 증가하는 경우입니다.

 

int[] arr = {1, 2, 3, 4, 5};

for (int i = 0; i < arr.length; i++) {
    for (int j = 0; j < arr.length; j++) {
        System.out.println(arr[i] + " " + arr[j]);
    }
}

 

 

배열 내 원소를 중복을 허용해 모든 순서쌍을 출력하는 코드입니다

보시다시피, 2개의 for문이 중첩되어 사용됩니다

배열 내 원소가 5개이며, print문은 총 25번 호출됩니다

배열 내 원소가 6개면, 36번,

배열 내 원소가 7개면, 49번과 같이 n^2번 연산됩니다

 

이와 같이 for문이 2중으로 중첩되어 있으면 O(n^2)와 같이 나타냅니다.

물론 꼭 n^2번 연산하지 않더라도, 빅 오(Big-O) 표기법은 최악의 경우를 고려하므로

for문이 이중으로 중첩되어 있으면 O(n^2)와 같이 나타냅니다

 

 

int[] arr = {1, 2, 3, 4, 5};

for (int i = 0; i < arr.length; i++) {
    for (int j = 0; j < arr.length; j++) {
        for (int k = 0; k < arr.length; k++) {
            System.out.println(arr[i] + " " + arr[j] + " " + arr[k]);
        }
    }
}

 

그럼 위와 같은 3중 for문의 코드의 시간복잡도는 어떻게 표현할 수 있을까요?

배열 내 원소의 개수가 5일 땐 125번,

6개일땐 216번,

7개일땐 512번.

원소의 개수가 n개라면 n^3번 연산합니다.

for문이 중첩될수록 제곱의 횟수가 증가합니다.

즉, for문이 k번 중첩되어 있다면 O(n^k)와 같이 나타낼 수 있습니다.

 

다만, O(2n), O(3n)을 데이터가 커질수록 상수의 영향력이 줄어들어 O(n)으로 나타내었던 것과 달리

O(n^3), O(n^4)과 같이 거듭제곱 형태의 경우 O(n^k)의 경우엔 데이터가 커지더라도

상수의 영향력이 여전이 크므로 O(n^3), O(n^4)와 같이 나타냅니다.

 

 

 

O(log n)

 

 

이번엔 log n의 시간복잡도를 가지는 경우입니다.

컴퓨터의 경우 이진법을 사용하기에 주로 밑이 2인 로그를 사용합니다.

 

고등학교를 졸업한지 꽤 되서 가물가물 하지만 log를 떠올려봅시다.

로그란 어떤 수를 구하기 위해 밑을 몇 번 곱해야 하는지 나타낼 때 썼었죠?

 

 

 

 

때문에 로그 함수는 지수 함수의 역함수이며, 이를 그래프로 그렸을 때

y = x^2와 y= log x(밑=2)는 y=x를 기준으로 대칭이다. 점점 생각이 납니다.

 

O(n^2)가 자료량이 커짐에 따라, 그 연산횟수(=시간)이 제곱으로 증가해 매우 빨랐다면,

O(log n)은 자료량의 증가에 따른 연산횟수의 증가가 자료량의 증가량보다 적다고 볼 수 있습니다.

 

 

이를 가장 잘 나타낼 수 있는 것은 이진탐색입니다.

 

 

병뚜껑 숫자 맞히기 게임은 특정 숫자를 외치면 Up, Down을 말하여 병뚜껑의 숫자를 찾는 게임입니다.

이진탐색을 쉽게 말하면 정중앙을 탐색하는 탐색 방법입니다.

병뚜껑 숫자가 1~50범위라면 25를 외치고 down 이라면, 이제 1~24 범위 중 중앙인 12를 말하는 방법이죠.

 

병뚜껑 숫자가 10, 최소 1, 최대 50이라네요.

한 명씩 번갈아가며 숫자를 이야기해봅시다. 다만 이진탐색적 기법으로.

1턴 : 25 -> down, 남은 범위 : 1 ~ 24

2턴 : 12 -> down, 남은 범위 : 1 ~ 11

3턴 : 6 -> up, 남은 범위 : 7 ~ 11

4턴 : 9 -> up, 남은 범위 : 10 ~ 11

5턴 : 10 -> 정답!

어떤가요? 매 탐색을 진행할 때 마다 탐색해야 할 범위가 절반으로 줄어듭니다.

 

때문에 1~50 범위의 수가 1~100 범위로 2배 증가해도, 탐색 횟수는 평균 1회밖에 증가하지 않습니다.

1~200으로 4배 증가하더라도, 탐색 횟수는 평균 2회밖에 증가하지 않고요.

 

 

이를 코드로 나타내면 다음과 같습니다.

 

int start = 1;
int end = 50;
int target = 10;

while (start <= end) {
    int mid = (start + end) / 2;
    if (mid == target) {
        System.out.println("정답 " + target + "을(를) 찾았습니다.");
        break;
    } else if (mid < target) {
        start = mid + 1;  // 오른쪽 반으로 범위 조정
    } else {
        end = mid - 1;  // 왼쪽 반으로 범위 조정
    }
}

 

O(log n)의 시간복잡도를가지는 이진 탐색의 경우,

데이터가 2배 늘어나면 탐색횟수가 1회,

데이터가 4배 늘어나면 2회,

8(2^3)배 늘어나면 3회,

16(2^4)배 늘어나면 4회,

n배 커지면, log_2 n번 증가합니다.

 

때문에 O(log n)은 O(n) 보다 더 효율적이라고 볼 수 있지요.

 

 

 

마치며

사실 공간복잡도와 관련된 글을 쓰고 싶어 시간복잡도와 공간복잡도를 비교하는 글을 쓰다가,

생각보다 길어져 별도의 글로 포스팅했습니다.

공간복잡도 편에서 다시 만나요.