복잡도 (Complexity) (2) - 시간복잡도

복잡도란 알고리즘의 성능을 나타내는 척도이며 시간복잡도(Time complexity)는 특정한 크기의 입력에 대해 알고리즘이 시간을 얼마나 소요하는지를 나타낸다. 시간복잡도를 표현할 때는 일반적으로 빅오표기법을 사용한다.

알고리즘 문제를 풀 때 단순히 '복잡도'라고 한다면 시간복잡도를 의미한다. 코딩 테스트에서의 시간제한은 시간내에 문제를 풀어야 한다는 제한보다는 작성한 프로그램이 모든 입력을 받아서 이를 실행하고 결과를 출력하는 데 까지 소요되는 시간의 제한을 의미한다. 

시간복잡도를 계산할 때 N개의 데이터에 대한 연산의 횟수에 의존하는 경우가 많다. 아래의 예시들을 통해서 시간복잡도를 이해해본다.

예시1)

위의 예시는 N=5의 데이터의 총합을 계산하는 코드이다. 이 때 연산횟수는 데이터의 개수인 N에 비례하는 것을 알 수 있다. 물론 sum의 값을 0으로 초기화 하는 연산과 sum의 값을 출력하는 연산도 존재하지만 N이 증가함에 따라 이 연산의 횟수는 무시할 수 있을 정도가 될 것이다. 

따라서 위의 소스코드에서 가장 영향력이 큰 부분은 데이터의 개수인 N에 비례하는 연산을 수행하는 for 반복문이므로 시간복잡도는

O(N) 이라고 표현한다.



예시2)

이 소스코드가 가지는 시간복잡도는 다음과 같다. num1과 num2에 각각 10, 20을 초기화 해주는 연산과 합을 출력하는 함수를 무시하면 이 코드가 실행하는 연산(더하기 연산)의 횟수는 1이다. 이는 상수 연산에 해당하므로 시간복잡도는 

O(1)로 표현한다.

 

예시3)

위의 예시에 해당하는 소스코드의 시간복잡도는 어떠할까?

이 소스코드 또한 예시1과 동일하게 N=5인 데이터 개수를 가지며, 데이터 개수에 따라서 2중 for문에 의해 N^2의 연산을 수행하게 된다. 따라서 시간복잡도는 O(N^2)이라는 것을 확인할 수 있다. 단순히 2중 반복문이라서 N x N번 연산을 수행한 것도 있지만 모든 2중 반복문이 O(N^2)의 시간복잡도를 가지는 것은 아니다. 반복문 내에서 내부적으로 다른 함수를 호출하게 된다면 다른 시간복잡도를 가질 수도 있기 때문이다. 따라서 소스코드를 정확히 분석한 후에 시간복잡도를 계산해야 한다.

아래의 표는 데이터의 개수 N에 대한 시간복잡도 표이다. 이 표에서 위쪽에 위치할 수록 더 빠르다는 것을 의미하며, 시간복잡도에 따라서 명칭이 존재한다.

빅오 표기법	명칭
O(1)	상수 시간(Constant time)
O(log N)	로그 시간(Log time)
O(N)	선형 시간
O(N log N)	로그 선형 시간
O(N^2)	이차 시간
O(N^3)	삼차 시간
O(2^N)	지수 시간

 

---

 

그러나 '실제 코딩 테스트' 에서는 차수가 작은 항들을 완전히 무시할 수 없는 경우도 존재한다.                                                                만약 연산횟수가 3N^3 + 5N^2 + 1,000,000인 알고리즘이 있다면 빅오 표기법 상으로는 차수가 가장 큰 항만 고려하여 O(N^3)이 된다. 그러나 N이 충분히 큰 숫자가 아니라면 1,000,000이라는 상수를 무시하기는 곤란할 것이다. 일반적인 코딩 테스트에서는 상수를 고려해야 할 경우가 적지만, 빅오 표기법이 항상 절대적인 것은 아니라는 점을 기억해두자.

일반적인 코딩 테스트에서의 시간 제한은 1 ~ 5초가량이다. CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서는 연산 횟수가 10억을 넘어가면 C언어를 기준으로 1초 이상의 시간이 소요된다. (파이썬에서는 더 많은 시간이 소요된다.) 예를 들어 N=1000이라면 O(N^3)의 알고리즘을 사용하게 되면 시간 초과일 가능성이 커지게 되므로 다른 알고리즘을 사용해야 할 경우가 생기게 되는 것이다. 따라서 문제에서 주어진 데이터 개수 등의 문제 조건을 잘 파악한 후 사용할 수 있는 알고리즘의 범위를 좁혀나가는 전략을 채택하는 것이 유리할 수 있다. 

일반적으로 코딩 테스트에서 문제를 풀 때의 예시 몇 가지를 나열한다. (모두 시간 제한이 1초인 문제에 대한 예시)

• N의 범위가 500인 경우 : O(N^3)인 알고리즘을 설계하면 시간 제한을 무사히 통과할 수 있다.
• N의 범위가 2,000인 경우 : O(N^2)인 알고리즘을 설계하면 시간 제한을 무사히 통과할 수 있다.
• N의 범위가 100,000인 경우 : O(N log N)인 알고리즘을 설계하면 시간 제한을 무사히 통과할 수 있다.
• N의 범위가 10,000,000인 경우 : O(N)인 알고리즘을 설계하면 시간 제한을 무사히 통과할 수 있다.