시간 복잡도(Time Complexity), 공간 복잡도 (Space Complexity)
시간 복잡도(Time Complexity)
시간 복잡도의 가장 간단한 정의는 알고리즘의 성능을 설명하는 것이다.
따라서 시간 복잡도는 프로세스가 수행해야하는 연산을 수치화한 것이라고 볼 수 있다.
컴퓨터 성능에 따라 실행시간은 달라질 수 있으므로, 실제 실행 시간보다는 명령문의 실행 빈도수를 계산하여 실행 시간을 구한다.
시간 복잡도는 주로 Big-O 표기법을 사용하여 나타낸다.
Big-O 표기법은 '입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?'를 표기하는 방법이다.
공간 복잡도 (Space Complexity)
공간 복잡도란 프로그램 실행과 완료에 얼마나 많은 공간(메모리)가 필요한지를 나타낸다.
알고리즘을 실행시키기 위해 필요한 공간(space)는 두 가지로 나눌 수 있다.
- 알고리즘과 무관한 공간, 즉 고정 공간
- 코드가 저장되는 공간, 알고리즘 실행을 위해 시스템이 필요로 하는 공간 등
- 알고리즘과 밀접한 공간, 즉 가변 공간
- 문제를 해결하기 위해 알고리즘이 필요로 하는 공간. 변수를 저장하는 공간, 순환 프로그램일 경우 순환 스택(recursion stack) 등
시간 복잡도 vs 공간 복잡도
시간 복잡도는 얼마나 빠르게 실행되는지, 공간 복잡도는 얼마나 많은 자원(메모리 공간)이 필요한지를 판단한다.
시간 복잡도와 공간 복잡도는 반비례하는 경향이 있어, 보통 알고리즘의 성능을 판단할 때는 시간 복잡도를 위주로 판단한다.
빅오(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)이 되며, 이 경우 시간 복잡도의 증가율이 다른 것들보다 훨씬 가파르다.
Scirpt
---------------------------------------
시간 복잡도에 한번 알아보았다. 반복문을 사용하다보면 이중 for을 가끔 사용하거나 수십만개의 데이터중 한개의 데이터를 찾을때 아무 생각 없이 코드를 작성하다 보면 1분에서 10분 이상 걸리수가 있다. 우리가 인터넷을 사용할때 10초만 걸려도 너무 느리고 답답함을 느끼는데 1분이라는 시간이 걸리면 고객들은 금방 나가게 된다. 그러니 코드만 짠다고 완성되는게 아니라 코드를 다 짜고나서 자신의 코드가 시간 복잡도가 얼마나 될까? 생각을하고 너무 오래 걸리면 더 짧은 방법은 없는지 확인을 해야한다.