2021_04_19

TIL - Time Complexity

1. Time Complexity (시간 복잡도)

우리가 알고리즘을 작성할 때 한번쯤은 Time Complexity (시간 복잡도)에 대해 들어봤을 것이다.
알고리즘에서의 시간 복잡도란 '입력값의 변화에 따라 문제를 해결하는 데 걸리는 시간의 비율이 어떻게 변화하는가'를 나타낸 것이다. 이에 따르면, 효율적인 알고리즘은 입력값이 증가함에 따라 시간이 증가하는 비율을 최소화한 알고리즘 이라고 할 수 있다.

시간 복잡도를 표기하는 방법 중 가장 대표적인 방법이 Big-O 표기법 이다. 최악의 경우 입력값이 증가함에 따라 시간이 얼마나 증가하는지 표기하는 방법이다. 따라서 오늘은 Big-O 표기법의 종류에 대해 공부한다.

1) O(1)
constant complexity라고 부르며, 입력값이 증가해도 시간은 늘어나지 않음을 이야기한다. 예를 들어, 아래와 같은 알고리즘이 있다고 해보자.

function 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

위 알고리즘에서는 배열과 인덱스를 인자로 넘겨 배열의 인덱스에 해당하는 값을 리턴하는 함수이다. 위 알고리즘을 수행하는 시간을 1초라고 가정했을 때, arr의 길이가 50, 100으로 늘어나도 해당 인덱스만 찾으면 되는 것이기 때문에 걸리는 시간은 똑같이 1초가 걸릴 것이다.

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

2) O(n)
linear complexity라고 부르며 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다. 예를 들어 아래와 같은 알고리즘이 있다고 해보자.

function O_n_algorithm(n) {
	for (let i = 0; i < n; i++) {
          console.log(i);
	}
}
function another_O_n_algorithm(n) {
	for (let i = 0; i < 2n; i++) {
	  console.log(i);
	}
}

O_n_algorithm 에서는 i를 1씩 증가하며 n까지 i를 출력하는 함수이다.
입력값(n)이 증가할 때마다 코드의 실행시간이 증가한다. 즉, 입력값이 증가함에 따라 같은 비율로 걸리는 시간이 늘어나고 있다.

another_O_n_algorithm에서도 마찬가지이다. 그대신 2n씩 늘어나고 있기 때문에 O(2n) 이지만 Big-O 표기법에서는 O(n)이라고 표기한다. n이 점점 증가할수록 그 비율은 엄청나게 커지기 때문에 계수는 점점 의미를 잃어가기 때문이다.

3) O(log n)
logarithmic complexity라고 하며, 이진 탐색 트리와 관련이 있다.
알고리즘이 수행될 떄마다 반씩 줄어들면서 수행을 한다. 예를들어 다음과 같은 코드가 있다고 해보자.

let i = n;
while(parseInt(i) > 0) {
 i = i / 2;
}

위 알고리즘은 n을 입력받아 while문 안에서 계속해서 1/2씩 줄어들고 있다.
따라서 시간 복잡도는 O(log n) 이라고 할 수 있다.

4) O(n^2)
quadratic complexity 라고 부르며 입력값이 증가함에 따라 걸리는 시간이 제곱의 비율로 증가하는 것을 의미한다. 예를들어 아래와 같은 알고리즘이 있다고 해보자.

function O_quadratic_algorithm(n) {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
	            console.log(j);
		}
	}
}

n을 1로 입력받았을 경우, 1초가 걸린다고 가정해보자. 그렇다면 n을 5로 입력받을 경우에는 5^2의 시간이 걸린다. 따라서 시간 복잡도는 O(n^2)이다.

5) O(2n)
exponential complexity 라고 부르며 알고리즘이 수행될 때마다 시간이 2배로 걸리는 것을 의미한다.
예를들어 아래와 같은 알고리즘이 있다고 해보자.

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

n번째 피보나치 수를 구하기 위해서는 n-1, n-2 번째 피보나치 수를 구해야하므로 1+2+4+8+ ... + 2^(n-1) 번 연산을 해야한다. 따라서 시간 복잡도는 O(2n)이다.


지금까지 배운 표기법의 시간복잡도 크기를 비교하면 다음과 같다.

이번시간에는 Big-O 표기법과 시간복잡도에 대하여 공부하였다.
내일은 알고리즘에 대하여 조금 더 공부하는 시간을 갖는다.
오늘은 여기까지ㅣ!!``