01 시간 복잡도란?

시간복잡도(time complexity)란? 알고리즘의 성능을 나타내는 지표로, 입력 크기에 대한 연산 횟수의 상한을 의미합니다. 시간 복잡도는 낮으면 낮을수록 좋습니다. 예를 들어, 어떤 문제를 해결하는 알고리즘 A,B,C가 있을 때 시간 복잡도가 가장 낮은 알고리즘이 A라면 A를 사용하는게 좋다.

1차원 배열 검색하기

1차원 배열에 값이 있을 때 특정 값을 배열의 맨 앞에서 순서대로 검색한다고 해보자. 이 때 연산 횟수가 가장 적을때와 많을 때는 언제일까?

가장 적은 경우는 검색 시작 위에 찾는 값이 바로 있는 경우일 것이고, 많은 경우는 찾는 값이 아예 없거나 가장 마지막에 위치하는 경우일 것이다.

알고리즘 수행 시간을 측정하는 방법

알고리즘 수행시간 측정 방법으로는 절대 시간을 측정하는 방법과 시간 복잡도를 측정하는 방법이 있습니다.

절대 시간을 측정하는 방법

배열에서 검색하는 프로그램을 작성한 다음에 프로그램을 실행하여 결과가 나올 때까지의 시간을 측정하면 됩니다.

그러나 이 방법은 프로그램을 실행하는 환경에 따라 달라질 수 있기에 코테에서 잘 활용하지 않습니다.

시간 복잡도를 측정하는 방법

시간 복잡도는 알고리즘이 시작한 순간부터 결괏값이 나올 때까지의 연산 횟수를 나타냅니다.

그리고 시간 복잡도를 측정한결과는 다음과 같이 최선(best), 보통(normal), 최악(worst)의 경우로 나눕니다.

앞에서 설명한 ‘1차원 배열 검색하기’ 알고리즘 처럼 특정한 입력 크기에 따른 연산 횟수로 시간 복잡도를 이야기 하는 것은 특정 상황에 한한 것이므로 무의미합니다.

코딩 테스트에서 알고리즘의 성능을 측정할 떈 2가지가 중요합니다.

첫째, 최악의 경우를 고려하라

코딩테스트에서는 아주 다양한 조합으로 입력값을 넣어 여러분의 코드를 평가합니다. 그 중에는 최악의 입력값도 있을 겁니다. 그러나 우리는 최악의 경우를 기준으로 시간 복잡도를 분석해야 합니다.

둘째, 알고리즘 성능은 정확한 연산 횟수가 아닌 추이를 활용한다.

우리가 확인하는 것은 정확한 연산 횟수는 아니다. 내 알고리즘이 제한 시간 안에 수행될 수 있을지를 파악해야한다. 따라서 우리는 숫자 하나하나를 고려하여 구한 정확한 연산 횟수가 아닌, 추이를 활용해 성능을 측정합니다.

코딩 테스트에서 알고리즘의 성능을 측정할 때, 연산 횟수의 추이만 알고 있어도 성능을 충분히 가늠할 수 있고, 정확한 연산 횟수를 구할 때보다 빠르다는 장점이 있습니다. 이런 방식으로 충분히 큰 입력값 N에 따른 연산 횟수의 추이를 활용하여 시간 복잡도를 표현하는 방법을 점근적 표기법이라고 합니다.

그리고 코딩 테스트에서 모든 경우의 수에서 알고리즘이 문제를 처리하는 것을 고려해야 하므로 시간 복잡도는 최악의 경우를 가정하여 이야기하는 것이 일반적입니다.

최악의 경우 시간 복잡도를 표현하는 빅오 표기법(Big-O notation)

최악의 경우에 대하여 시간 복잡도를 표현하는 방법은 무엇이 있을까요? 가장 많이 사용하는 점근적 표기법은 상한선을 활용하는 방법입니다. 이 표기법을 빅오 표기법이라고 합니다.

어떤 프로그램의 연산 횟수가 f(x)라고 할 때 함수의 최고차항을 남기고 계수를 지워 O(…)와 같이 표기하면 됩니다. 예를 들어 어떤 프로그램의 연산 횟수가 f(x) = 2x^2 + 3x + 5 라면 시간 복잡도를 O(x^2)과 같이 표현하면 됩니다.

상한선은 빅오 표기법, 하한선은 빅 오메가 표기법으로 표시합니다.

수식	빅오표기	설명
3x^2 + 5x + 6	O(x^2)	다항함수로 구성되어 있으므로 최고차항 x^2만 남습니다.
x + log x	O(x)	다항함수와 로그함수로 구성되어 있으므로 증가폭이 더 낮은 로그함수는 사라지고 다항함수만 남습니다.
2^x + 10x^5 + 5x^2	O(2^x)	지수함수는 다항함수보다 빠르게 증가하므로 지수함수만 남습니다.
5x^2 - 6x	O(x^2)	최고차항 x^2만 남습니다.

그나저나 왜 이렇게 표기할까?

빅오 표기법으로 최악의 시간 복잡도를 표기하는 방법 자체가 어렵지는 않습니다. 그런데 이 식은 어디서 나온걸까요? 아래 예시 코드를 확인해보자.

function solution(n) { 
	let count = 0;
	// 반복문 1 : n^2번 연산 수행
	for (let i = 0; i < n; i += 1) {
		for (let j = 0; j < n; j += 1) {
			count += 1;
		}
	}
	
	// 반복문 2 : n번 연산 수행
	for (let k = 0; k < n; k += 1) {
		count += 1;
	}
	
	// 반복문 3 : 2n번 연산 수행
	for (let i = 0; i < 2 * n; i += 1) {
		count += 1;
	}

	// 반복문 4 : 5번 연산 수행
	for (let i = 0; i < 5; i += 1) {
		count += 1;
	}
	
	console.log(count); //  59(n이 6일 때, 6^2 + 6 + 2 * 6 + 5 = 59)
}

solution(6); // 함수 호출

solution() 함수는 주석 영역별로 각각 n^2, n + 2n, 5번의 증가 연산을 하며 결괏값은 곧 연산 횟수를 의미합니다. 지금의 경우 solution(6)을 호출하면, 6^2 + 6 + 2 * 6 + 5, 즉, 연산횟수는 59입니다. 이때 solution()함수는 식으로 다음과 같이 표현할 수 있습니다.

이때 다음을 만족하는 C가 있으면 f(x)의 최악의 시간 복잡도는 O(g(x))라고 쓰는 겁니다.

• 특정 x 시점 이후부터 항상 f(x) ≤ C* g(x)를 만족.
• C는 상수.

→ 이게 뭔소릴까.

쉽게 말해 g(x)에 상수 C를 곱했을 때 특정 시점부터 f(x)를 넘어서는지 여부를 보면 됩니다.

C는 2, g(x)는 x^2일때의 그래프 예시.

(이미지 출처: https://wikidocs.net/222560)

그래프를 보면 대략 x = 4부터 항상 2x^2가 f(x)를 넘으므로 위 공식을 만족합니다. 하지만 위 공식을 만족하는 g(x)는 하나만 있을까요?

“g(x) = x, C = 50인 경우 x에 값을 몇개 넣어보니 f(x)보다 값이 크네…? 그렇다면 시간 복잡도는 O(x)라고 해도 되는 것아닐까?”

→ 조금만 생각해보면 아니라는 걸 알 수 있습니다. 왜냐면, 50x는 대략 x = 47에서 다시 역전되기 때문이죠. 이런 이유로 f(x) = x^2 + 3x + 5의 시간 복잡도는 O(x^2)라고 쓸수있습니다.

빅오 표기법을 쉽게 쓸 때는 왜 최고차항만 남기고 계수를 지울까?

앞서 빅오표기법은 다음과 같이 f(x)의 최고차항만 남기고 계수를 지워 O(…)와 같이 쓸수있다고 했습니다. 어떻게 이렇게 되는지 설명해드림.

• f(x) = x^2 + 3x + 5 에서 최고 차항인 x^2만 남김
• x^2는 앞의 계수가 1이므로 제거할 것이 없음
• 시간 복잡도는 O(x^2)

(이후 다양한 함수의 시간 복잡도를 비교한 예시는 생략한다.)

→ 우리가 시간복잡도에서 구하는 것은 상한의 정확한 값이 아니라 ‘이 정도 될 것이다’의 파악하는 추이이기에 우리가 우선적으로 파악해야할 것은 상한을 구하는 목적인 알고리즘의 성능을 가늠할 수 있는 가장 의미 있는 상한을 구하는 게 중요합니다.

시간 복잡도를 코딩 테스트에 활용하는 방법

시간 복잡도를 표현하는 방법이 빅오 표기법이라는 것은 알았는데 어떻게 활용해야할까? 코딩테스트 문제에는 제한 시간이 있으므로 문제를 분석한 후에 빅오 표기법을 활용해서 해당 알고리즘을 적용했을 때 제한 시간 내에 출력 값이 나올 수 있을지 확인해 볼 수 있습니다. 그러면 문제 조건에 맞지 않는 알고리즘을 적용하느라 낭비하는 시간을 줄일 수 있습니다.

코딩테스트의 문제들은 출제자가 의도한 로직을 구현했다면 대부분의 코드를 정답 처리할 수 있도록 채점 시간을 충분히 여유있게 지정합니다. 따라서 연산 횟수를 1000-3000만 정도로 고려해서 시간 복잡도를 생각하면 됩니다. 예를 들어 제한 시간이 1초인 문제는 연산 횟수가 3000만이 넘는 알고리즘은 사용하면 안됩니다. 제한 시간이 1초인 문제에 각 시간 복잡도 별로 허용할 수 있는 최대 연산 횟수는 다음과 같이 생각하면 됩니다.

언어별로 성능은 다를 수 있으나, 특정 언어가 유리하거나 불리하면 안되기에 언어에 따른 성능차이를 고려하진 않아도 됩니다.

시간 복잡도별 최대 연산 횟수를 기계처럼 외울 필요는 없습니다. 표를 보면 연산 횟수의 간격이 매우 큽니다. 그 이유는 여러분이 구현한 코드의 시간복잡도가 문제에서 요구하는 성능을 만족하면 모두 통과할 수 있도록 충분히 여유를 두기 때문입니다. ‘이 정도 되는구나’ 감을 잡으면 되고, 다른 책에서는 O(N)이면 1000만이라고 했는데, 왜 여기선 1000만 ~ 2000만이라고 하는지 고민하기보다는, ‘대략 데이터가 1000만개 정도면 O(N)을 사용해야 하는구나’ 감을 익히는 식으로 학습하는 걸 추천합니다.

맨 처음 우리가 살펴본 배열에서 검색하기 방식을 보면 하나하나 짚어가며 찾는 방식은 시간복잡도가 O(N)입니다. O(N)이 허용하는 연산 횟수는 1000만이므로 데이터 개수가 1000만개 이하면 이 알고리즘을 사용해도 됩니다. 바로 이렇게 시간 복잡도를 활용하여 문제가 제시하는 제한 시간을 초과하는 알고리즘을 제거하면 됩니다.

02 시간 복잡도 계산해보기

시간 복잡도를 실전으로 계산해보자. 몇 가지 상황을 보며, 시간 복잡도를 계산하는 방법을 익혀두면 다른 문제를 풀 때도 시간 복잡도를 수월하게 계산해볼 수 있을 것이다.

1. 문제 정의 부터 시작해서
2. 연산 횟수를 측정한 후
3. 시간 복잡도를 분석하는

순서로 공부를 해보자.

별 찍기 문제

별 찍기 문제는 숫자 N을 입력받으면 N번째 줄 까지 별을 1개부터 N개까지 늘려가며 출력하라는 것입니다.

푸는 과정

우선 연산 횟수를 구합니다. 지금은 출력 자체가 연산입니다. 1번째 줄은 1번 연산, 2번째 줄은 2번 연산, … , N번째 줄은 N번 연산합니다.

결국 연산 횟수는 f(N)는 다음과 같습니다. 빅오 표기법으로는 O(N^2)이라고 할 수 있겠습니다.

박테리아 수명 문제

초기 박테리아 세포 개수가 N일 때 해마다 세포 개수가 이전 세포 개수의 반으로 준다면 언제 모든 박테리아가 죽을지 계산해야 합니다.

푸는 과정

예를 들어 N이 16인 경우, 모든 박테리아는 5년이면 소멸합니다.

현재 박테리아 수가 N이라면, 1년 뒤 박테리아 수는 ½ N이라고 할 수 있습니다. Y년 후의 박테리아의 수는 (½)^Y N입니다.

그러면 박테리아의 소멸 시기는 (½)YN의 값이 최초로 1보다 작아질 때입니다. 수식으로는 (½)YN <= 1인 Y를 찾으면 됩니다. 이 수식은 다음과 같이 정리할 수 있습니다.

이를 통해 이 알고리즘은 O(logN)의 시간 복잡도를 가진다는 것을 알 수 있습니다.

앞으로 문제를 풀 때 특정 값을 계속 반으로 줄이는 동작을 한다면 시간 복잡도를 O(log N)이라 생각하면 됩니다. 시간 복잡도가 O(log N)인 문제들은 이후 정렬이나 이진 트리를 공부하면서 다시 보겠습니다.

지금까지 빅오 표기법으로 알고리즘의 효율을 분석하는 방법을 분석하는 방법을 공부했습니다. 코딩 테스트에서 시간 복잡도를 이해하고 분석하는 것은 매우 중요합니다.

리마인드

• 입력 크기에 따른 연산 횟수의 추이를 활용해서 시간 복잡도를 표현하는 방법을 점근적 표기법이라고 합니다.
• 시간 복잡도를 빅오 표기법으로 나타내려면 데이터 개수 N 에 대해 연산 횟수를 일반화한 후 최고차항을 남기고 개수 N에 대해 연산 횟수를 일반화한 후 최고 차항을 남기고 계수를 제거하면 됩니다.