O(nm), O(n^3), O(m^n), O(sqrt(n)), 그래프 추가
일반적으로 알고리즘의 성능 분석은 실행에 필요한 공간 측면에서 분석하는 공간 복잡도,
실행 소요시간 측면에서 분석하는 시간 복잡도를 추정하여 평가한다.
시간 복잡도(Time Complexity)
시간 복잡도의 가장 간단한 정의는 알고리즘의 성능을 설명하는 것이다.
따라서 시간 복잡도는 프로세스가 수행해야하는 연산을 수치화한 것이라고 볼 수 있다.
컴퓨터 성능에 따라 실행시간은 달라질 수 있으므로, 실제 실행 시간보다는 명령문의 실행 빈도수를 계산하여 실행 시간을 구한다.
시간 복잡도는 주로 Big-O 표기법을 사용하여 나타낸다.
Big-O 표기법은 '입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?'를 표기하는 방법이다.
빅오(Big-O) 표기법
알고리즘 성능을 수학적으로 표시해주는 표기법이다.
알고리즘의 실행시간보다는 데이터나 사용자 증가율에 따른 알고리즘 성능을 예측하는 것이 목표이므로, 중요하지 않은 부분인 상수와 같은 숫자는 모두 제거한다.
즉, 빅오 표기법은 불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적으로 사용된다.
여기서 측정되는 복잡성에는 시간 복잡도와 공간 복잡도가 있다.
- 시간 복잡도 : 입력되는 n의 크기에 따라 실행되는 조작의 수
- 공간 복잡도 : 알고리즘이 실행될 때 사용하는 메모리 양
다음은 대표적인 Big-O의 복잡도를 나타내는 차트이다.
Big-O 표기법의 종류
O(1)
Constant Time (상수)
입력 데이터 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘이다.
다음과 같은 함수가 있을 때, 함수의 인자로 어떤 배열이 들어오더라도 처리 시간과 성능에 변화가 없다.
이런 경우에 시간 복잡도를 O(1)이라고 한다.
// O(1)
const findO1 = (arr) => {
// 배열의 첫 번째 인자가 0이면 true, 아니면 false 반환
return arr[0] === 0 ? true : false;
};O(n)
Linear Time (선형)
입력 데이터의 크기에 비례해서 처리 시간이 걸리는 알고리즘이다.
n이 1 늘어날 때마다 처리 시간이 1 증가하여 처리 시간이 선형적으로 증가한다.
(즉, n의 크기만큼 처리 시간 증가)
이런 경우에 시간 복잡도를 O(n)이라고 한다.
// O(n)
const findO2 = (arr) => {
// arr 배열을 돌면서 원소를 모두 출력
arr.map((a) => console.log(a));
};O(log n)
O(log n)의 대표적인 알고리즘은 이진 검색(binary search)이다.
ex) 위에서 정렬된 숫자 1~9에서 key값이 6인 숫자를 검색하는 것을 보여준다.
처음에 중간 값인 5부터 확인하여 비교한다.
(key값이 더 크므로 왼쪽은 비교할 필요가 없고, 오른쪽만 비교한다.)
오른쪽에서 중간인 7을 비교한다.
(key값이 더 작으므로 오른쪽은 비교할 필요가 없고, 왼쪽만 비교한다.)
남은 공간에서 중간인 6을 비교한다. key값과 동일하므로 종료한다.// O(logn)
const findO5 = (key, start, end) => {
for (let i = start; i <= end; i++) {
arr.push(i);
let m = (start + end) / 2;
if (arr[m] === key) {
console.log(m);
} else if (arr[m] > key) {
return findO5(key, start, m-1);
} else {
return findO5(key, m+1, end);
}
}
};이렇게 한 번 반복할 때마다, 처리해야하는 값이 절반씩 사라지는 알고리즘의 시간 복잡도를 O(log n)이라고 한다.
이는 데이터가 증가해도 성능에는 큰 차이가 없음을 알 수 있다.
따라서, O(log n)은 순차 검색 O(n)보다도 훨씬 빠르며,
Big-O 표기법 중에서 O(1) 다음으로 빠른 시간 복잡도를 가지는 알고리즘이다.
O(n^2)
Quadratic Time
입력 데이터의 크기의 제곱만큼 비례하여 처리 시간이 증가하는 알고리즘이다.
다음 함수에서 인자로 이차원 배열이 들어오는 경우, 배열의 크기가 커질수록 처리 시간은 제곱하여 증가한다.
// O(n^2)
const findO3 = (array) => {
array.forEach((arr) => {
arr.forEach((a) => {
console.log(a);
});
});
};인자로 들어오는 배열의 크기가 작다면 처리 시간이 그리 오래 걸리지 않지만, 크기가 커질수록 처리 시간이 기하급수적으로 증가한다.
O(2^n)
Exponential Time
2n과 같이 n이 하나씩 증가할 때마다 걸리는 시간이 배로 증가하기 때문에
Big-O 표기법 중 가장 느린 시간 복잡도를 가진다.
재귀 함수로 구현하는 피보나치(Fibonacci) 수열로 비유할 수 있다.
// O(2^n)
const findO4 = (n) => {
// 피보나치 수열
if (n <= 0) return 0;
else if (n === 1) return 1;
return findO4(n - 1) + find(n - 2);
};피보나치 수열의 트리 구조는 다음 그림과 같다.
매번 함수가 호출될 때마다, 2번씩 또 호출하는데 이를 트리의 높이만큼 반복하면 피보나치 수열이다.
이것의 시간 복잡도가 곧 O(2^n)이 되며, 이 경우 시간 복잡도의 증가율이 다른 것들보다 훨씬 가파르다.
