코드를 작성하다가 실행시켜보면 어떤 코드는 바로 결과값이 나오고 어떤건 시간이 좀 걸리는 경험을 한 적이 있었다. 알고보니 이런 문제들이 시간 복잡도라는 것과 연관 있었던 것이다!
시간 복잡도가 무엇일까?
아침에 일어나 학교를 가야하는 상황이다. 두 가지의 선택지가 있는데 첫 번째는 걸어가기, 두 번째는 버스를 타고 가는 것이다. 걸어서는 10분이 걸리지만 버스를 타면 5분밖에 걸리지 않는다. 결과만 보면 당연히 버스를 타는게 더 빠르지만 버스정류장을 가는 시간, 기다리는 시간, 하차해서 걸어가는 시간 등을 고려하면 걸어가는 것과 비슷하거나 오히려 더 거릴지 모른다. 이렇게 모든 면을 고려하면 차라리 걸어가는 선택을 할 것이다. 뛰어가면 오히려 더 빠를 수도 있으니까.
이처럼 등교시간을 줄이려고 더 나은 선택을 하려하는 것처럼 어떠한 코드를 작성했을 때 이 코드가 얼마나 걸리는지 예측해보는 것을 시간 복잡도라고 합니다.
아래는 시간 복잡도를 그래프(점근 표기법)로 나타낸 것입니다.
시간 복잡도를 표현하는 방법은 여러가지가 있지만 가장 대중적인 표현법으로 Big-O표현법을 사용하겠습니다. Big-O는 문제의 크기가 N일 때, 시간이 얼마나 걸리는지를 O(N)으로 표현하는 방법입니다. N이 커질수록 시간이 더 많이 걸리는 방식입니다.
위 그림을 보면 아래 초록색(O(log n), O(1))에 가까울수록 수행시간이 짧은 알고리즘이고 붉은색에 가까울수록 수행시간이 오래 걸리는 알고리즘입니다.
비교 분석
O(1)
function print(arg) {
console.log(arg)
}
print("Hello World");함수 내부의 코드가 한 번만 실행되기 때문에 O(1)으로 표현됩니다. 입력 데이터의 크기에 영향을 받지 않습니다.
O(log n)
function logn(key, arr, s, e) {
if (s > e) {
return -1;
}
m = (s + e) / 2;
if (arr[m] === k) {
return m;
} else if (arr[m] > key) {
return logn(key, arr, s, m-1);
} else {
return logn(key, arr, m+1, e);
}
}인자에 key값, 배열, 시작하는 수, 끝나는 수를 입력받으면 그 배열에 key값을 찾는데 절반을 잘라내고 못찾으면 또 그 반에서 반을 나눠서 없는 부분을 없애고를 반복하며 찾아내는 방식입니다. 크게크게 없애기 때문에 반복문 보다 더 빠른 처리속도를 보입니다.
O(n)
function loop(n) {
for(let i = 0; i < n; i++) {
console.log(i);
}
}
loop(10)loop함수 내부에서 n만큼 반복합니다. n이 10이면 10만큼 처리시간이 증가합니다.
O(n^2)
function loop2(n) {
for(let i = 0; i < n; i++) {
console.log(i);
for(let j = 0; j < n; j++) {
console.log(j);
}
}
}
loop2(10)loop2함수 안에 for반복문 두 개가 겹쳐져서 실행되기 때문에 n이 10이라면 n^2(n의2승)만큼 증가합니다.
위에 O(n)에 비하면 10배 더 걸린다는 뜻입니다.
O(2^n)
function pibo(n, r) {
if (n === 0) return 0;
else if (n === 1) return r[n] = 1;
return r[n] = pibo(n - 1, r) + pibo(n - 2, r)피보나치 수열처럼 1, 1, 2, 3, 5, 8, 13...처럼 늘어나서 O(n^3)보다 더 급격하게 수행시간이 늘어납니다.
O(nm)
function loop2(n, m) {
for(let i = 0; i < n; i++) {
console.log(i);
for(let j = 0; j < m; j++) {
console.log(j);
}
}
}
loop2(10)O(n^2)와 비슷해보이지만 인자가 두개라서 n값이 10,000이고 m값이 10이라면 100,000만큼 처리시간이 걸립니다.
기출 변형
function loops(n) {
for (let i = 0; i < n; i++) {
console.log(i);
}
for (let j = 0; j < n; i++) {
console.log(j);
}
}그렇다면 위 코드는 O(2n)만큼 걸린다! 라고 볼 수 있지만 Big-O표기법에서는 그냥 O(n)이라고 합니다.
왜냐하면 Big-O표기법은 상수는 신경쓰지 않기 때문입니다.
왜그런거죠?
💡 Big-O는 실제 알고리즘의 러닝타임을 측정하기 위해 만들어진 것이 아닌 장기적으로 데이터가 증가함에 따른 처리시간의 증가율을 예측하기 위해 만들어진 것이기 때문입니다.
💡 따라서 증가율에 초점이 맞춰져 있어서 상수로 얼마나 증가하던지 신경쓰지 않습니다!
