시간 복잡도 (Big-O)

시간 복잡도

입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?

시간 복잡도를 표기하는 방법은 다음과 같습니다.

• Big-O(빅-오)
• Big-Ω(빅-오메가)
• Big-θ(빅-세타)

위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법입니다.

Big-O 표기법

세 가지 시간 복잡도 표기법 중 Big-O 표기법이 가장 자주 사용됩니다.

최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문입니다.

 

O(1) constant complexity

입력값이 증가하더라도 시간이 늘어나지 않습니다. 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있습니다.

// O(1)의 시간 복잡도를 가진 알고리즘
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

O(n) linear complexity

입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미합니다.

입력값이 1일 때 1초의 시간이 걸리고, 입력값을 100배로 증가시켰을 때 1초의 100배인 100초가 걸리는 알고리즘을 구현했다면, O(n)의 시간 복잡도를 가진다고 할 수 있습니다.

// O(n)의 시간 복잡도를 가진 알고리즘
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
	}
}

 

입력값이 커지면 커질수록 계수(n 앞에 있는 수)의 의미(영향력)가 점점 퇴색되기 때문에, 같은 비율로 증가하고 있다면 2배가 아닌 5배, 10배로 증가하더라도 O(n)으로 표기합니다.

 

O(log n) logarithmic complexity

Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가집니다. BST(Binary Search Tree)가 O(log n)의 예시입니다.

BST에선 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어듭니다.

 

이해하기 쉬운 게임으로 비유해 보자면 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(n2) quadratic complexity

입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미합니다.

예를 들어 입력값이 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸리게 된다면,

이 알고리즘의 시간 복잡도는 O(n2)라고 표현합니다.

// 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)로 표기합니다. n이 커지면 커질수록 지수가 주는 영향력이 점점 퇴색되기 때문에 이렇게 표기합니다.

 

O(2n) exponential complexity

Big-O 표기법 중 가장 느린 시간 복잡도를 가집니다.

 

종이를 42번 접을 수 있다면 그 두께가 지구에서 달까지의 거리보다 커집니다. 고작 42번 만에 얇은 종이가 그만한 두께를 가질 수 있는 것은, 매번 접힐 때마다 두께가 2배로 늘어나기 때문입니다.

 

구현한 알고리즘의 시간 복잡도가 O(2n)이라면 다른 접근 방식을 고민해 보는 것이 좋습니다.

// O(2n)의 시간 복잡도를 가진 알고리즘
function fibonacci(n) {
	if (n <= 1) {
		return 1;
	}
	return fibonacci(n - 1) + fibonacci(n - 2);
}

재귀로 구현하는 피보나치 수열은 O(2n)의 시간 복잡도를 가진 대표적인 알고리즘입니다. 브라우저 개발자 창에서 n을 40으로 두어도 수초가 걸리는 것을 확인할 수 있으며, n이 100 이상이면 평생 결과를 반환받지 못할 수도 있습니다.