시간복잡도와 공간복잡도
CS에서는 하나의 문제에 대하여 여러 알고리즘을 사용하여, 다양한 방식으로 해결할 수 있다. 이때 어떠한 솔루션이 최적인지 판단하기 위한 기준이 필요하다.
이때, 기준은 알고리즘을 수행하는 시스템 및 구성과는 독립적 이어야하고, 입력된 수와 상관관계를 나타낼 수 있어야한다.
이를 만족하는 기준이 시간복잡도 와 공간복잡도 이다.
점근적 표기법 Big-Ω, Big-θ, Big-O
알고리즘의 성능은 입력의 크기가 충분히 클 때의 성능이 중요하다. 그래서 알고리즘의 수행 시간은 항상 입력의 크기가 충분히 클 때를 분석한다. 즉, 입력 `n -> ∞`일 때를 분석하기 위해 점근적 분석을 해야한다.
O (빅오, Big-O)
•
최악의 경우(Worst Case)를 나타낸다. 즉, 최대로 걸릴 수 있는 시간(상한 시간)을 의미한다.
Ω (빅오메가, Big-Omega)
•
최선의 경우(Best Case)를 나타낸다. 즉, 최소로 걸릴 수 있는 시간(하한 시간)을 의미한다.
θ (빅세타, Big-Theta)
•
최선과 최악의 중간(Average Case)을 나타낸다. 즉, 평균적인 복잡도를 의미한다.
3가지 표기법을 제시하지만, 알고리즘의 성능 측정 지표로 주로 사용되는 것은 빅오 표기법이다. 그 이유는 ‘아무리 최악의 상황이라도 보장할 수 있는 상한 시간의 성능’ 표기 필요성과 알고리즘이 복잡해질수록 평균적인 경우를 구하는 것의 어려움 때문이다.
시간복잡도 (Time Complexity)
시간복잡도는 알고리즘의 수행시간에 관한 분석 기준이다.
알고리즘의 절대적인 실행 시간을 나타내는 것이 아닌, 알고리즘을 수행하는데 기본 연산들이 몇 번 이루어지는 지를 입력된 데이터 N에 관한 함수 형태로 표현한다.
(여기서 기본 연산은 데이터 입출력, 산술연산, 제어연산 등을 이야기한다)
시간복잡도는 일반적인 빅오 표기법으로 나타낸다. 점근적 표기법이므로 연산 횟수가 다항식으로 표현될 경우, 최고차항을 제외하면 모든 항과 최고차항의 계수를 제외시킨다.
O(1) 상수 시간 (Constant time)
입력 크기(n)에 상관없이 일정한 연산을 수행하면, 시간복잡도 O(1)
function printnumber(n: number) {
console.log(n)
}
JavaScript
복사
O(logn) 로그 시간 (Logarithmic time)
아래 예시는 반복할 때마다 i값이 2배로 증가한다. 2^k = n(k는 반복횟수) 일 경우 종료되며, 양쪽에 로그를 씌우면 k = logn이 된다. 따라서 O(logn)의 시간복잡도를 갖는다.
for (i = 1; i <= n; i*2) {
console.log(i);
}
JavaScript
복사
O(n) 선형 시간 (Linear time)
입력 크기 n에 비례하여 연산 횟수가 선형적으로 증가하는 경우, 시간복잡도는 O(n)이다.
for (i = 0; i < n; i++) {
console.log(i);
}
JavaScript
복사
O(n^2) 2차 시간 (Quadratic time)
입력 크기가 n 에 비례하여 연산 횟수가 n^2의 형태로 증가하면 시간복잡도는 O(n^2)이다.
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
console.log(i, j);
}
}
JavaScript
복사
O(2^n) 지수 시간 (Exponential time)
입력 크기가 n 일때 연산 횟수가 2^n의 형태로 증가하면 시간복잡도는 O(2^n)이다.
function recursive(n: number) {
if (n <= 1) return n;
return recursive(n-1) + recursive(n-2);
}
TypeScript
복사
공간복잡도 (Space Complexity)
공간복잡도는 알고리즘의 메모리 사용량에 관한 분석 기준이다. 최근에는 컴퓨터 성능의 발달로 메모리 공간이 여유로워져 제약이 많이 사라졌고, 이에 따라 공간복잡도의 중요성이 비교적 적어져 최근 시간복잡도를 우선시 하는 경향이 있다.
일반적으로 공간복잡도 역시 시간복잡도처럼 최악의 경우(worst case)를 빅오 노테이션으로 표기한다.
일반적으로 공간이 하나 생성되는 것을 1이라고 표현한다. 아래의 공간복잡도는 O(1)이다.
const a = 1;
JavaScript
복사
아래의 경우 역시 O(1)의 공간복잡도를 갖는다. 아래 예시에서 n 회 반복되는 것은 공간복잡도에 영향을 끼치지 않으며, 지역변수 i와 res만을 사용하기 때문에 상수 공간복잡도를 갖는다.
function factorial(n: number) {
int i = 0;
int res = 1;
for (i = 1; i <= n; i++) {
res *= i;
}
return res;
}
TypeScript
복사
아래의 예시는 O(n)의 공간복잡도를 갖는다. n의 값에 따라 재귀적으로 함수를 호출하며, stack 에는 n부터 1까지 모든 값이 쌓이게 된다.
function factorial(n: number) {
if (n > 1) {
return n * factorial(n-1);
}
else return 1;
}
TypeScript
복사
공간복잡도만을 고려할 경우, 고정 공간보다는 가변 공간의 자료구조들을 사용하는 것이 효율적이다.
함수 호출 시 할당되는 지역 변수들이나 동적 할당되는 객체들도 모두 공간이 필요하다.
재귀 함수를 사용할 경우, 매 호출마다 매개변수 , 지역변수, 함수의 복귀 주소 를 저장할 공간이 필요하게 된다.
따라서 재귀적(Recursive)으로도, 반복문으로도 구현할 수 있다면 반복문으로 구현하는 것이 공간복잡도 측면에서 좋다고 볼 수 있다.