[자료구조/알고리즘]

Chapter - 시간 복잡도

---

문제를 해결하기 위한 알고리즘 로직을 코드로 구현하기 위해서는 시간 복잡도를 고려해야한다.

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

효율적인 알고리즘을 구성했다는 것은 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성했다는 말이다.

시간 복잡도를 표현하는 방법에는 여러가지가 있지만, 그중 Big-O 표기법으로 시간복잡도를 나타내 보겠다.

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(rteault)

위의 알고리즘에서는 입력값의 크기가 아무리 커져도 즉시 출력값을 얻어낼 수 있다. 예를 들어 arr의 길이가 100만이라도 즉시 해당 index에 접근해 값을 반환할 수 있다.

O(n)

---

O(n)은 linear Complexity라고 부르며 입력값이 증가함에 따라 시간또한 같은 비율로 증가하는 것을 의미한다. 예를들어 입력값이 1일 때, 1초의 시간이 걸리고 입력값을 100배로 증가시키면 1초의 100배인 100초가 걸리는 알고리즘이 O(n)의 시간 복잡도를 갖고 있다고 얘기할 수 있다.

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

O_n_algorithm 함수에서는 입력값이 1증가할 때마다, 코드의 실행 시간이 1초씩 증가하게 된다. 즉, 입력값이 증가함에 따라 같은비율로 걸리는 시간이 늘어나고 있다. 만약 같은 비율이 아닌 2배, 5배, 100가 된다고 하더라도 O(n)으로 표현한다.

O(log n)

---

O(log n)은 logarithmic Complexity라고 부르며 Big-O표기법중 O(1)다음으로 빠른 시간 복잡도를 갖는다. 자료구조에서 나왔던 BST(Binary Search Tree)에선 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어든다.

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

O($n^2$)

---

O(n2)은 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
		}
	}
}

2n, 5n 을 모두 O(n)이라고 표현하는 것처럼, $n^3$과 $n^5$도 모두 O($n^2$)로 표기한다.

O($2^n$)

---

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

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