[CS] Time Complexity Day-46

시간 복잡도

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

• 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성했다는 이야기입니다.

시간 복잡도는 주로 빅-오 표기법을 사용해 나타냅니다.

Big-O 표기법

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

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)

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

ex) O(2n)일 경우 결과 값의 반환 시간이 2배씩 증가한다는 뜻입니다. 또 다른 예시로 5n이 될경우 결과 반환 시간이 5배 증가한다고 볼 수 있습니다.

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(log n)

O(1) 다음으로 빠른 시간 복잡도를 가집니다.
BST(Binary Search Tree)에서 원하는 값을 탐색할 때, 노드를 이동할 때 마다 경우의 수가 절받으로 줄어듭니다.

O(n^2)

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

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
			}
		}
	}
}

O(2^n)

exponential complexity라고 부르며 Big-O 표기법 중 가장 느린 시간 복잡도를 가집니다.

구현한 알고리즘의 시간 복잡도가 O(2^n)일 경우 다른 접근 방식이 요구됩니다.

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