Time Complexity

알고리즘 문제를 풀다보면 문제에 대한 해답을 찾는것이 가장 중요하지만 그에 못지않게 효율적인 방법을 찾는것도 중요하다.

효율적인 방법을 고민한다는 것은 시간 복잡도를 고민한다는 말과 같은것이다.

 

시간복잡도와 Big-O(빅-오)표기법에 대해 배워보자

 

👊 시간 복잡도

---

 

시간 복잡도를 고민한다 
= 입력값의 변화에 따라 연산을 실행할때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?

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

 

시간 복잡도는 주로 빅-오 표기법을 사용하여 나타내준다.

👊 Big-O 표기법

• Big-O(빅-오) - 최악
• Big-Ω(빅-오메가) - 최선
• Big-θ(빅-세타) - 중간(평균)

이 중에서 빅-오 표기법이 가장 많이 사용된다. 빅-오 표기법의 경우 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문에 더욱 바람직하다. (최악의 경우가 발생하지 않기를 바라고 그 부분을 제외해서 시간을 계산하는것보다 최악의 경우도 고려하여 대비하는것이 더욱 좋다)

 

🎟 O(1)

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

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

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

arr의 길이가 100만이라도, 즉시 해당 index에 접근해 값을 반환할 수 있다.

 

 

🎟 O(n)

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

예를 들어 입력값이 1일 때, 1초의 시간이 걸리고, 입력값을 100배로 증가시켰을때 1초의 100배인 100초가 걸리는 알고리즘을 구현했다면, 그 알고리즘은 O(n)의 시간 복잡도를 가진다고 할 수 있다. 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
	}
}

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와 비슷하다.

 

BST의 값 탐색도 같은 로직으로 O(log n)의 시간 복잡도를 가진 알고리즘(탐색기법)이다.

 

🎟 O(n2)

 

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)

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

종이를 42번 접으면 그 두께가 지구에서 달까지의 거리보다 커진다는 이야기를 들어본적이 있나?

고작 42번만에 얇은 종이가 그만한 두께를 가질 수 있는것은 매번 접힐때마다 두께가 2배로 늘어나기 때문이다.

// O(2n)의 시간 복잡도를 가지는 알고리즘 예시

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

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

브라우저 개발자 창에서 n을 40으로 두어도 수초가 걸리는것을 확인할 수 있으며, 

n이 100이상이면 평생 결과를 반환받지 못할 수도 있다.