알고리즘/시간 복잡도

시간 복잡도 (Time Complextity)

• 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘
• 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계

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 (arr의 길이가 100이라도 즉시 index를 통해 값 반환 가능)

---

O(n)

• linear complexity
• 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것 (n에 비례한다)

//입력값이 1일 때 1초의 시간이 걸리고, 입력값을 100배로 증가시켰을 때 1초의 100배인 100초가 걸리는 알고리즘
function O_n_algorithm(n) {
	for (let i = 0; i < n; i++) {
	// do something for 1 second
	}
}

//입력값이 1 증가할때마다 코드의 실행 시간이 2초씩 증가 (O(2n)이지만, 같은 비율로 증가하고 있다면 2배,5배,10배 증가하더라도 그대로 O(n)으로 표기)
function another_O_n_algorithm(n) {
	for (let i = 0; i < 2n; i++) {
	// do something for 1 second
	}
}

---

O(log n)

• logarithmic complexity
• O(1) 다음으로 빠른 시간 복잡도 (log n에 비례한다)

ex) BST에서 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어든다.

1. 1~100 중 하나의 숫자를 플레이어1이 고른다 (30을 골랐다고 가정합니다).
2. 50(가운데) 숫자를 제시하면 50보다 작으므로 down을 외친다.
3. 1~50중의 하나의 숫자이므로 또다시 경우의 수를 절반으로 줄이기 위해 25를 제시한다.
4. 25보다 크므로 up을 외친다.
5. 경우의 수를 계속 절반으로 줄여나가며 정답을 찾는다. (최악의 경우에도 7번이면 답 찾기 가능)

---

O(n^2)

• quadratic complexity
• 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가
  • 입력값이 1일때 1초가 걸리던 알고리즘에 5라는 입력값이 주어지면 25초가 걸려용

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)로 표기
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
• 가장 느린 시간 복잡도

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

---

데이터 크기에 따른 시간 복잡도

N의 크기	허용 시간 복잡도
N ≤ 11	O(N!)
N ≤ 25	O(2^N)
N ≤ 100	O(N^4)
N ≤ 500	O(N^3)
N ≤ 3,000	O(N^2lgN)
N ≤ 5,000	O(N^2)
N ≤ 1,000,000	O(Nlgn)
N ≤ 10,000,000	O(N)
그 이상	O(lgN),O(1)