시간 복잡도
시간 복잡도란?
프로그램을 작성할 때 입력의 크기에 따라서 프로그램이 계산하는 횟수가 크게 달라진다. 시간복잡도는 알고리즘을 실행하는데 필요한 시간 척도이며, 알고리즘 효율성을 판단하는 중요 척도 중 하나다. 프로그램 수행에 걸리는 절대적인 시간이 아닌, 알고리즘을 수행하는데 사용되는 연산들이 몇 번 이루어지는가에 대한 것을 상대적 지표로 나타낸 것이다.
시간 복잡도의 특징
1. 시간복잡도의 산정기준은 연산수이다.
소요되는 기본 연산 수에 의거한다. 주로 알고리즘이 사용한 기본 연산의 수에 따르며 기본 연산이란 데이터의 비교, 덧셈, 곰셈, 나눗셈 등이 있다.
2. 시간복잡도는 함수적으로 표현한다.
입력 크기에 대한 함수적 관계를 나타낸다. 기본 연산 수가 입력 크기와 어떤 함수 관계가 있는지를 이를 함수식처럼 표현한다.
3. 시간복잡도는 점근적 분석방법을 쓴다.
입력 크기가 무한히 증가할 때, 알고리즘이 어떻게 작동하는가에 대해서 따질 때, "점근적 분석 방법"을 사용한다. 여기서 점근적 분석방법이란 상계/상한(최악, 빅오), 하계/하한(최선, 빅 오메가), 평균(빅 세타)을 말한다.
평균적인 경우를 가장 많이 사용할 것 같지만, 알고리즘이 복잡해 질수록 평균적인 경우는 구하기가 너무 어려워지기 때문에 최악의 경우로 알고리즘의 성능을 파악합니다.
시간 복잡도의 분석 종류
1. big-O(빅 오 표기법)
최악의 경우를 나타낸다.(상한 접근)
2. big-Omega(빅 오메가 표기법)
최적의 경우를 나타낸다.(하한 접근)
3. big-Theta(빅 세타 표기법)
평균을 나타낸다. (big-O 와 big-Omega 값의 평균값)
시간 복잡도의 주요 표기
1. O(1) - 상수 시간(Constant time)
입력 크기(n)에 상관없이 일정한 연산을 수행하면 시간 복잡도는 O(1)이다. 다음의 알고리즘은 n에 상관 없이 한번만 연산을 수행한다.
function constantTime(n) {
console.log(n);
}
때문에 다음과 같은 시간복잡도를 가진다.
T(n) = O(1)
2. O(logN) - 로그 시간
입력 크기(N)가 커질 때 연산 횟수가 logN에 비례해서 증가하면 시간 복잡도는 O(logN)이다. 다음의 알고리즘은 i값이 반복될 때마다 2배씩 증가한다.
for (let i = 1; i <= n; i *= 2) {
console.log(i);
}
위의 알고리즘을 k번 반복했을 때, 2k = N이 되고 반복문이 종료된다. 양쪽에 로그를 취하면 다음과 같다.
log2(2k) = log2N k = log2N
k는 수행 횟수이기 때문에 다음과 같은 시간복잡도를 가진다.
T(n) = logN
3. O(n) - 선형 시간
입력 크기(n)가 커질 때 연산 횟수가 n에 비례해서 증가하면 시간복잡도는 O(n) 이다. 다음의 알고리즘은 n만큼 반복문을 수행한다.
for (let i = 1; i < n; i++) {
console.log(i);
}
n의 값에 비례해서 연산수가 선형적으로 증가하기 때문에 다음과 같은 시간복잡도를 가진다.
T(n) = O(n)
4. O(n2) - 2차 시간
입력 크기(n)가 커질 때 연산 횟수가 n2에 비례해서 증가하면 시간복잡도는 O(2)이다.
for (let i = 0; i < n; i++) {
for (let j = 0; j < n + 1; j++) {
console.log(i, j);
}
}
위 알고리즘은 for문이 중첩되어 있기 때문에 n2에 비례해서 연산수가 증가한다. 시간복잡도는 다음과 같다.
T(n) = O(n2)
5. O(2n) - 지수 시간
입력 크기(n)가 커질 때 연산수가 2n에 비례해서 증가하면 시간 복잡도는 O(2n)이다. 다음의 알고리즘은 피보나치 수를 구하는 알고리즘이다.
function fibonacci(n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
한번 함수를 호출할 때 마다 두번씩 재귀로 함수를 호출하기 때문에 2n에 비례해서 연산수가 증가한다. 시간복잡도는 다음과 같다.
T(n) = O(2n)
시간복잡도 성능 지표
오른쪽으로 갈수록 시간복잡도가 큰 알고리즘이다. n의 값이 작을 때는 알고리즘 사이에 큰 차이는 없지만 n의 값이 커지면 커질수록 복잡한 알고리즘은 수행시간이 급격히 떨어진다.