Time Complexity

시간 복잡도

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

• 대부분의 문제는 실행 시간 : 1초에 가깝게 디자인이 된다. (보통 1억번의 연산당 1초)
  1초가 걸리는 입력의 크기 (외우자)

  • O(N) : 100,000,000
  • O(NlogN): 5,000,000
  • O(N^2): 10,000
  • O(N^3): 500
  • O(2^N): 26
  • O(N!): 11

Big-O 표기법

• Big-O(빅-오) : 최악 - "이 정도 시간까지 걸릴 수 있다"
  빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문에 가장 자주 사용됩니다.
• Big-Ω(빅-오메가) : 최선 - "최소한 특정 시간 이상이 걸린다"
• Big-θ(빅-세타) : 중간 (평균) - "이 정도 시간이 걸린다"

결과를 반환하는 데 최선의 경우 1초, 평균적으로 1분, 최악의 경우 1시간이 걸리는 알고리즘을 구현했고, 최선의 경우를 고려한다고 가정하겠습니다. 이 알고리즘을 100번 실행한다면, 최선의 경우 100초가 걸립니다. 만약 실제로 걸린 시간이 1시간을 훌쩍 넘겼다면, 어디에서 문제가 발생한 거지?란 의문이 생길 겁니다. 최선의 경우만 고려하였으니, 어디에서 문제가 발생했는지 알아내기 위해서는 로직의 많은 부분을 파악해야 하므로 문제를 파악하는 데 많은 시간이 필요합니다.

평균값을 기대하는 시간 복잡도를 고려한다면 어떨까요?
알고리즘을 100번 실행할 때 100분의 시간이 소요된다고 생각했는데, 최악의 경우가 몇 개 발생하여 300분이 넘게 걸렸다면 최선의 경우를 고려한 것과 같은 고민을 하게 됩니다.

극단적인 예이지만, 위와 같이 최악의 경우가 발생하지 않기를 바라며 시간을 계산하는 것보다는 최악의 경우도 고려하여 대비하는 것이 바람직합니다.

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

O(log n)은 logarithmic complexity라고 부르며 Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가집니다.
자료구조에서 배웠던 BST(Binary Search Tree)를 기억하시나요?
BST에선 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어듭니다. 이해하기 쉬운 게임으로 비유해 보자면 up & down을 예로 들 수 있습니다.

O(N^2)

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(2^N)

O(2n)은 exponential complexity라고 부르며 Big-O 표기법 중 가장 느린 시간 복잡도를 가집니다.
종이를 42번 접으면 그 두께가 지구에서 달까지의 거리보다 커진다는 이야기를 들어보신 적 있으신가요?
고작 42번 만에 얇은 종이가 그만한 두께를 가질 수 있는 것은, 매번 접힐 때마다 두께가 2배로 늘어나기 때문입니다.

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

quiz

출처 : 코드스테이츠