[Algorithm] 시간 복잡도란?

학습 Point

• 시간복잡도
• 점근 표기법

 

코딩테스트에서 코드를 평가하는 방식은 크게 두 가지이다.

• 내가 작성한 코드의 결괏값이 테스트 케이스의 결과와 일치하는가?
• 문제에서 요구한 알고리즘의 성능을 만족하는가?

 

두 방식은 프로그래머스에서 문제를 풀 때 쉽게 볼 수 있는 '정확성'과 '효율성'이다.

결과가 일치하는 것은 쉽게 확인할 수 있다. 하지만 성능을 만족하는 것은 어떻게 확인해야 할까?

단순히 생각하자면 입력값을 넣고 출력값이 나올 때까지 걸리는 시간을 측정한다고 생각하면 되겠지만, 이는 컴퓨터의 성능 같은 다양한 외부 요인에 영향을 많이 받는다. 바로 여기서 시간복잡도의 개념이 등장한다.

 

시간복잡도란, 알고리즘의 성능을 나타내는 지표로, 입력 크기에 대한 연산 횟수의 상한을 의미한다. 연산 횟수는 전적으로 코드의 설계에 의존하기 때문에 서로 다른 알고리즘을 비교하기 용이한 일반적인 기준이 된다.

 

그렇다면 시간복잡도는 어떻게 표기해야 할까?

여기 크기 10을 가지는 배열이 있다.

 

 

왼쪽부터 순서대로 값을 비교하여 숫자를 검색하는 알고리즘을 짠 경우, 1을 찾기 위해서는 얼마나 비교해야 할까?

당연히 1은 맨 처음에 존재하니까 한 번이 된다. 이는 값을 가장 빨리 찾은 경우이다.

반대로 가장 늦게 찾은 경우는 찾는 값이 제일 마지막에 존재하거나 아예 존재하지 않는 경우가 된다. 이때 비교 횟수는 배열의 크기인 10이 된다.

 

이 배열에서 숫자를 검색하는 알고리즘의 시간복잡도는 최소 1, 최대 10이 된다. 하지만 이것은 크기가 10인 배열에서 순차적으로 숫자를 찾을 때 유요한 결과이다. 만약 배열의 크기가 다르거나 숫자를 검색하는 방법이 다르다면 다른 결과가 나왔을 것이다.

그렇기 때문에 특정한 입력 크기에 한하여 시간복잡도를 계산해서는 안된다. 입력 크기를 N으로 일반화하여 연산 횟수의 추이를 활용해서 시간복잡도를 표현하는 방법을 점근 표기법이라고 한다.

 

코딩테스트에서는 모든 경우의 수를 고려하는 것이 일반적이기 때문에 시간복잡도는 최악의 경우를 늘 상정해야 한다. 최악의 경우를 기반으로 한 알고리즘 성능을 점근적 상한이라고 하며, 이를 빅오 표기법(Big-O)이라고 한다.

빅오 표기법은 어떤 알고리즘의 연산 횟수를 f(x)라고 하였을 때, 최고차항을 계수만 지워 표기하면 된다.

예를 들어, 2x² + 3x + 5의 연산 횟수를 가진다면, O(x²)라고 표기할 수 있다.

최고차항만 남기는 이유는, x가 무한하게 증가한다면, 최고차항 아래의 차항은 최고차항에 비해 무시해도 될 만큼 작아질 것이다. 가장 큰 영향을 끼치는 최고차항으로만 판단하면 된다.

참고로 최선의 경우는 빅오메가, 평균적인 경우는 빅세타라고 한다.

 

점근 표기법은 실제 코딩테스트에 어떻게 적용할 수 있을까? 컴퓨터가 초당 연산할 수 있는 횟수는 최대 1억 번이라고 한다. 코딩테스트의 문제는 채점 시간을 보다 여유 있게 가지기 때문에 약 1,000만 ~ 3,000만 정도로 시간복잡도를 고려한다면 아래 표와 같이 연산 횟수를 정리할 수 있다.

 

시간복잡도	사용 예시	최대 연산 횟수
O(1)	배열의 인덱스를 통한 원소 접근	1
O(logN)	이진탐색	10억
O(N)	순차탐색	1,000~2,000만
O(NlogN)	정렬	100만
O(N2)	행렬곱셈, 다항식 계산	3,000~5,000
O(2N)	부분집합 구하기, 하노이탑	20~25
O(N!)	순열 생성,  외판원 문제(TSP)	10

 

 

 

---

 

 

다음 예제들을 풀어보면서 공부한 내용을 점검해보고자 한다.

 

1. 아래 다항식에 대해 점근적 상한을 구하라.

• Y = 2^X - 3X² + 5X
• Y = X² + X! - 2^X
• Y = 3X + logX - 4

첫번째는 지수함수와 다항함수가 주어져 있다. 지수함수의 증가율이 다항함수보다 크기 때문에 지수함수만 남기면 O(2^X)가 된다. 두 번째는 팩토리얼이 제일 크게 증가하기 때문에 O(X!)이 된다. 마지막은 로그함수는 증가율이 크지 않은 함수고, 상수는 고려하지 않기 때문에 O(X)가 된다.

 

 

2. 아래 문제를 읽고 점근적 상한을 구하라.

• 데이터가 N개인 배열을 순차탐색하는 경우
• 행과 열이 각각 N개인 행렬의 원소를 모두 더하는 경우
• N개의 동전을 던질 때 앞, 뒷면에 대한 모든 경우의 수

N개의 데이터를 순차탐색하는 경우는 하나씩 순차적으로 탐색하면 되므로 O(N)이 된다.

행과 열이 각각 N개인 행렬은 총 N²개의 원소를 탐색하는 경우니까 O(N²)가 된다.

마지막으로 N개의 동전의 앞뒤 경우의 수는 각 동전은 앞면과 뒷면 두 가지 경우의 수가 존재한다. 각 동전의 결과는 다른 동전과 상관없이 독립적인 경우이기 때문에 2를 N번 곱한 2^N이 된다. 그러므로 빅오 표기법으로 O(2^N)이다.

 

 

3. 간단한 문제를 풀고 시간복잡도를 점근 표기법으로 구하라.

https://school.programmers.co.kr/learn/courses/30/lessons/120819

프로그래머스

 

class Solution {
    public int[] solution(int money) {
        int[] answer = {money / 5500, money % 5500};
        return answer;
    }
}

다음 코드는 어떤 입력이라도 한번의 연산이면 결과가 출력되므로 O(1)이다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/120583

프로그래머스

 

class Solution {
    public int solution(int[] array, int n) {
        int answer = 0;
        for(int number : array){
            if(number == n)
                answer++;
        }
        
        return answer;
    }
}

배열을 순차적으로 탐색하기 때문에 배열의 크기 N만큼 연산한다. 즉, O(N)이 된다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/120848

프로그래머스

class Solution {
    public int solution(int n) {
        int fac = 1;
        int count = 0;
        
        while(fac <= n)
            fac *= ++count;
        
        return count - 1;
    }
}

N의 최대값이 3,628,800 임에도 불구하고 출력값은 고작 10이다. 사실상 상수나 다름없기 때문에 O(1)이라고 할 수 있겠다.