시간복잡도 (알고리즘 문제 활용)

[1] 시간 복잡도란?

시간 복잡도란, 알고리즘의 성능을 나타내는 지표로써 입력 크기에 따른 연산 횟수를 의미합니다. 시간 복잡도가 낮으면 입력 크기가 주어졌을 때 해결하는 속도가 빠르고, 높으면 해결하는 속도가 느려집니다. 따라서 시간 복잡도는 낮을수록 좋습니다.

[1-1] 알고리즘 수행 시간을 측정하는 방법

알고리즘 수행 시간을 측정하는 방법은 절대 시간 측정 방법과 시간 복잡도를 측정하는 방법이 존재합니다.

(1) 절대시간 측정 방법

절대 시간을 측정하는 방법은 입력 값에 따른 시간을 측정하면 됩니다. 아래 예시와 같이 linearSearch에서 입력값에 따른 시간을 측정하여 절대 시간을 측정합니다. 하지만, 코드를 실행하는 환경에 따라서 달라질 수 있으므로 잘 사용하지 않는 편입니다.

int main() {
    vector<int> arr = {1,2,3,4,5,6};
    int target = 4;
    // 시작 시간
    auto start = chrono::high_resolution_clock::now();
    // O(n) 선형 탐색
    int result = linearSearch(arr, target);
    // 끝 시간 기록
    auto end = chrono::high_resolution_clock::now();

    // 경과 시간 계산
    chrono::duration<double, milli> elapsed = end - start;
    // 결과 출력
    cout << "Result: " << result << endl;
    cout << "Time taken: " << elapsed.count() << " ms" << endl;
}

(2) 시간 복잡도 측정 방법

시간 복잡도는 입력값에 따른 결괏값이 나올 때까지의 연산 횟수로 연산 횟수는 결과에 따라서 최선, 보통, 최악으로 나눌 수 있습니다.

맨 앞부터 하나씩 검사하는 linearSearch에서 배열이 1~10까지의 숫자가 있을 때, 1의 숫자를 찾을 때는 1번 만에 찾지만 10이라는 숫자를 찾을 때는 10번 만에 찾게 됩니다. 따라서 최선은 1, 최악은 10이라는 연산 횟수입니다.

따라서, 알고리즘 성능을 측정할 때는 다음과 같은 두 가지 고려해야 합니다.

1. 최악의 경우를 고려
   linearSearch를 사용할 때 모든 타깃을 1번만에 찾기는 어렵다고 볼 수 있기 때문에 최악의 경우를 기준으로 시간 복잡도를 분석해야 합니다.
2. 알고리즘 성능은 연산 횟수가 아닌 추이를 활용
   목적은 제한 시간 안에 수행될 수 있는지 정도를 파악하면 충분하기에 연산 횟수가 아닌 추이를 활용하여 성능을 측정합니다. 해당 방법으로 충분히 큰 입력값 N에 따른 연산 횟수의 추이를 파악하여 시간 복잡도를 표현하는 방법을 점근적 표기법이라고 합니다.

 

 

[1-2] 빅오 표기법

점근적 표기법은 상한선을 활용하는 방법인데, 해당 표기법을 사용하는 것을 빅오 표기법이라고 합니다. 추이를 파악하기 때문에 함수의 최고차항을 남기고 계수를 지워 O(...)와 같이 표기합니다.

f(x) = 2x^5 + 3x + 4

연산 횟수가 f(x) 라면 최고차항인 2x^5를 남기고 계수를 지워서 x^5 만을 남겨서, 결국에는 f(x)의 시간 복잡도는 O(x^5)라고 표현하게 됩니다. 

f(x) = 2x^5 + 3x + 4를 C++코드로 표현하면 이렇습니다.

#include <iostream>
using namespace std;

// f(x)
int fX(int n) {
    int cnt = 0;
    for (int i = 0; i < 2; i++) {
        for (int i = 0; i < n; i++) {
            for (int i = 0; i < n; i++) {
                for (int i = 0; i < n; i++) {
                    for (int i = 0; i < n; i++) {
                        for (int i = 0; i < n; i++) {
                            cnt++;    
                        }    
                    }
                }
            }
        }
    }
    for (int i = 0; i < n * 3; i++) {
        cnt++;
    }
    for (int i = 0; i < 4; i++) {
        cnt++;
    }
    return cnt;
}

앞서 말한 f(x) = 2x^5 + 3x + 4는 빅오 표기법으로는 시간 복잡도가 O(x^5) 만을 남길 것입니다..

 

빅오 표기법은 왜 최고 차항만 남기고 계수를 지울까요?, 왜 이렇게 해도 되는지 아래의 그래프를 보며 이해하도록 하겠습니다. 아래의 그래프 그림을 통해서 여러 함수를 표현했습니다.

위의 그래프대로 표현한 함수 리스트는 아래의 테이블과 같습니다.

순서	수식	함수
1	y = x!	팩토리얼 함수
2	y = 2^x	지수함수
3	y = x^2	다항함수
4	y=xlogx	로그함수와 다항함수의 조합
5	y = x	다항함수
6	y = logx	로그함수
7	y=1	상수

1번 ~ 6번까지 앞서 말했던 x^5는 x값이 커질수록 y 값의 격차는 천천히 증가하는 일부(3x + 4)를 무시할 수 있을 정도로 커질 것입니다. 따라서, 상한이 정확한 값이 아니라 추이를 파악하는 이유입니다. 따라서 최고차항만을 고려해서 시간복잡도를 알아냅니다.

알고리즘을 문제를 풀기 전에 시간 복잡도를 고려한다면 알고리즘을 생각하는 시간을 줄일 수 있습니다. 백터 안에 숫자들이 정렬되어 있으면 이분 탐색법으로 O(logn)의 시간복잡도가 나오지만 , 선형 탐색으로 탐색하면 O(n)이 나오게 됩니다.  아래의 예제를 보겠습니다.

• O(n) - 선형탐색

// O(n)
int linearSearch(const vector<int>& arr, int target) {
	for (int i = 0; i < arr.size(); i++) {
		if (arr[i] == target) {
			return i; // 타겟 값을 찾으면 해당 인덱스 반환
		}
	}
	return -1; // 타겟 값을 찾지 못하면 -1 반환
}

• O(logn) - 이분탐색

// 시간복잡도 O(log n)
int binarySearch(const vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() -1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (target == arr[mid]) return mid;
        if (target < arr[mid]) right = mid -1; 
        if (target > arr[mid]) left = mid + 1;
    }
    return -1;
}

백터가 정렬되어 있으면 이분 탐색으로 탐색이 계속 반으로 줄어 탐색이 가능하게 됩니다. 이분탐색 시간복잡도를 O(logn)이라고 부릅니다.  어떤 문제를 해결하는 알고리즘이 O(n), O(logn)의 시간 복잡도를 가질 때, O(logn)을 선택하는 게 좋을 것입니다.

 

[1-3] 알고리즘 활용

절대 시간 측정은 컴퓨터 환경에 따라 달라진다고 했었습니다. 그래서, 저의 개인 컴퓨터로 연산 횟수 측정한 결과 약 10억 번 정도 연산을 하는 것 같습니다. 

✏️ Note
1초에 몇 번? 다양한 의견
- https://discuss.codechef.com/t/how-many-operations-can-be-done-in-2-sec-and-3-sec/58519/3 (코드셰프)
- https://codeforces.com/blog/entry/80680 (코드포스)
- https://www.acmicpc.net/board/view/39001 (백준)

위의 검색 결과, 다양한 의견이 있습니다. 1억 번 정도로 의견이 맞춰지기에 보수적으로 잡아서 C++ 기준으로 1초당 1000~3000만 번 정도라고 생각하고 알고리즘 문제 풀이에서 시간복잡도를 계산하는 것이 좋아 보입니다. 

앞서 말했듯이 계수와 나머지는 제거할 수 있을 정도로 입력값(x)이 커질수록 그래프 차이는 확연히 커지기에 일부를 계수 등을 제거할 수 있을 것입니다. 따라서, 상한을 구하되, 최소한의 상한을 구할 필요가 있습니다.

(1) 제한 시간 1초 (3000만 번)

1초라고 가정하고 각각의 시간복잡도 테이블을 보도록 하겠습니다. 

시간복잡도	N	최대 연산
O(N!)	10	약 300만
O(2^N)	20~25	약 100 ~ 3000만
O(N^3)	200~300	약 800만 ~ 2700만
O(N^2)	3,000~5,000	약 900만 ~ 2500만
O(NlogN)	100만	약 100만 ~ 2000만
O(N)	1,000 ~ 2,000만	1000만 ~ 2000만
O(logN)	10억	30번

 

• O(N!)
  O(N!)은 1에서 n까지 모든 자연수의 곱을 n에 상대하여 이르는 말로 기호는 느낌표(!)를 쓰며 팩토리얼이라고 읽습니다. O(N!)은 총경우의 수를 계산할 때도 쓰입니다. N! 은 N * (N-1) * (N-2) *... * 2 * 1 이 N이 라고 할 수 있습니다.
• O(2^N)
  O(2^N)은 입력 크기가 늘어나면 2배씩 늘어나게 됩니다. N이 3일 때에는 2 * 2 * 2으로 되어 있습니다.
• O(N^2)
  N에 따른 반복문이 2개 일 때 나타나게 됩니다. 예를 들면 2차원 배열을 검색할 때 사용하게 됩니다.
• O(logN)
  한 번 연산할 때마다 작업해야 할 양이 반으로 줄어들게 됩니다. 처음에 고민할 때 로그 밑이 없어서 의아해할 수 있는데 대부분 2로 생각하면 됩니다. 예를 들다면 2^5 =32가므로 N이 32이 일 때 5번만 탐색하면 된다는 의미입니다.
• O(1)
  어떤 N값이 들어와도 한 번에 구할 수 있는 경우를 말하게 됩니다.

✏️ Note
위의 테이블을 전부 암기를 하는 것보다 이 정도로 생각한다라고 감을 잡는 정도로 생각하면 될 것 같습니다.  

 

시간복잡도를 생각하여, 알고리즘 문제를 풀어나갈 때에 자신이 짠 코드가 시간 초과가 나는지 확인하여 개선하거나, 처음에 문제를 확인하고 알고리즘을 적용할 때 시간제한을 보며, 내가 사용하려고 하는 알고리즘은 해결할 수 있는지를 확인하고 알고리즘을 적용할 수 있기에 시간복잡도를 아는 것은 중요합니다.

 

참고문헌

박경록, 「코딩 테스트 합격자 되기 C++」의 편의 스터디에 참가하여 정리하며 작성한 글입니다.