시간 복잡도

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

시간복잡도 표기법

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

Big-O 표기법

Big-O 표기법은 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?를 표기하는 방법이다.

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

위 알고리즘에선 입력값의 크기가 아무리 커져도 즉시 출력값을 얻어낼 수 있다.

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)이라고 표현할 수 있다.

그러나 사실 이 알고리즘 또한 Big-O 표기법으로는 O(n)으로 표기한다.

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

O(log n)

O(log n)은 logarithmic complexity라고 부르며 Big-O표기법중 O(1)다음으로 빠른 시간 복잡도를 가진다.
BST(Binary Search Tree)와 up&down 게임을 예로 생각하면 쉽다.

O($n^2$)

O($n^2$)은 quadratic complexity라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.

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)이라고 표현하는 것처럼, $n^3$ 과 $n^5$도 모두 O($n^2$)로 표기한다.

O($2^n$)

O($2^n$)은 exponential complexity라고 부르며, Big-O 표기법 중 가장 느린 시간 복잡도를 가진다.
종이를 42번 접으면 그 두께가 지구에서 달까지의 거리보다 커진다는 전설....
매번 접힐때마다 두께가 2배로 늘어나기 때문.

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

피보나치!!