[TIL-20210720] [알고리즘] Time Complexity (시간복잡도)

Time Complexity(시간복잡도)

알고리즘을 푸는데 있어 해답을 찾는 것이 가장 중요하지만, 그만큼 효율적인 방법으로 문제를 해결하는 것도 중요하다. 효율적인 방법을 고민한다는 것은 시간 복잡도를 고려한다는 것과 같은 말이다. 알고리즘에서 시간복잡도를 고려한다는 말은 "입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?" 를 말한다. 따라서 시간복잡도를 고려해 효율적인 알고리즘을 구현한다는 것은 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성했다라는 이야기가 될 수 있다.

Big-O 표기법

시간복잡도를 나타내는 방법은 Big-O(빅-오) / Big-Ω(빅-오메가) / Big-θ(빅-세타)가 있는데 이 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법이다. 이 중에서 빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문에 주로 빅오(Big-O) 표기법을 이용하여 나타낸다.

Big-O 표기법 시간복잡도 그래프

O(1)

시간복잡도가 O(1)인 경우
O(1)는 constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다. 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다는 의미이다.

function O_1_algorithm(arr, index) {
	return arr[index];
}

let arr = [1, 2, 3, 4, 5];
let index = 1;
let result = O_1_algorithm(arr, index);
console.log(result); // 2

위 알고리즘에선 입력값(arr)의 크기가 아무리 커져도 즉시 해당 출력값(arr[index]값)을 얻어낼 수 있다.

O(n)

시간복잡도가 O(n)인 경우
O(n)은 linear complexity라고 부르며, 입력값에 따라 시간 또한 비례해서 증가하는 것을 의미한다.

function O_n_algorithm(n) {
	for (let i = 0; i < n; i++) {
	// do something for 1 second
	}
}

function another_O_n_algorithm(n) {
	for (let i = 0; i < 2n; i++) {
	// do something for 1 second
	}
}

O_n_algorithm 함수에선 입력값(n)이 1 증가할 때마다 코드의 실행 시간이 1초씩 증가한다. 즉 입력값이 증가함에 따라 같은 비율로 걸리는 시간이 늘어나고 있다는 것을 의미한다. 함수 another_O_n_algorithm 은 입력값이 1 증가할때마다 코드의 실행 시간이 2초씩 증가한다. 그럼 이 알고리즘은 O(2n)의 시간복잡도 가진다고 생각할 수 있지만, 입력값(n)이 커질수록 계수의 영향력이 줄어들기 때문에 2배, 5배, 10배로 증가한다해도 O(n)으로 표기한다.

O(log n)

시간복잡도가 O(log n)인 경우
O(log n)은 logarithmic complexity라고 부르며 Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가진다. 자료구조에서 배웠던 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어드는 BST(Binary Search Tree)를 예시로 들어 이해하기 쉬운 게임으로 비유해 보자면 up & down을 예로 들 수 있다.

1. 1~100 중 하나의 숫자를 플레이어1이 고른다 (30을 골랐다고 가정합니다).
2. 50(가운데) 숫자를 제시하면 50보다 작으므로 down을 외친다.
3. 1~50중의 하나의 숫자이므로 또다시 경우의 수를 절반으로 줄이기 위해 25를 제시한다.
4. 25보다 크므로 up을 외친다.
5. 경우의 수를 계속 절반으로 줄여나가며 정답을 찾는다.

매번 숫자를 제시할 때마다 경우의 수가 절반이 줄어들기 때문에 최악의 경우에도 7번이면 원하는 숫자를 찾아낼 수 있게 된다. BST의 값 탐색도 같은 로직으로 O(log n)의 시간 복잡도를 가진 알고리즘(탐색기법)이다.

O(n^2)

시간복잡도가 O(n^2)인 경우
O(n^2)은 quadratic complexity라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다. 예를 들어 입력값이 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸리게 된다면, 이 알고리즘의 시간 복잡도는 O(n2)라고 표현한다.

function O_quadratic_algorithm(n) {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
		// do something for 1 second
		}
	}
}

function another_O_quadratic_algorithm(n) {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			for (let k = 0; k < n; k++) {
			// do something for 1 second
			}
		}
	}
}

2n, 5n 을 모두 O(n)이라고 표현하는 것처럼, n3과 n5 도 모두 O(n2)로 표기한다. 이 커지면 커질수록 지수가 주는 영향력이 점점 퇴색되기 때문이다.

O(2^n)

시간복잡도가 O(2^n)인 경우

O(2^n)은 exponential complexity라고 부르며 Big-O 표기법 중 가장 느린 시간 복잡도를 가진다. 2^n만큼 증가한다는 것은 입력값(n)이 커질때 마다 시간이 2배로 늘어난다는 것을 의미한다. 기하급수적으로 늘어난다는 뜻이다. 구현한 알고리즘의 시간 복잡도가 O(2n)이라면 다른 접근 방식을 고민해 보는 것이 좋다.

function fibonacci(n) {
	if (n <= 1) {
		return 1;
	}
	return fibonacci(n - 1) + fibonacci(n - 2);
}

재귀로 구현하는 피보나치 수열은 O(2^n)의 시간 복잡도를 가진 대표적인 알고리즘이다.