복잡도에 대해
우리가 알고리즘 문제풀이 등을 진행하다 보면 실제 예시의 테스트는 통과하시만, 결과확인 테스트에서 효율성 문제로 실패하는 경우가 발생한다. 이는 내가 작성한 알고리즘 코드가 일정의 효율을 결과테스트에서 만족하는 만큼까지 끌어올리지 못해서 발생하는 경우이다.
이 처럼 코드는 특정 작업을 수행할 때에 어떻게든 돌아가게 만들 수야 있지만, 더 빠르고 더 적은리소스를 사용하도록 만드는게 관건이다.
이러한 코드의 효율성의 척도가 되는 것을 복잡도라고 한다. 복잡도는 시간복잡도와 공간복잡도로 나뉠 수 있다.
시간복잡도와 공간복잡도는 각각 대개 Big-O 표기법으로 표현된다.
Big-O 표기법은 알고리즘의 시간 복잡도나 공간 복잡도를 최악의 경우에 대한 상한을 나타내는 표기법으로 미리 Big-O표기법에 대한 포스팅에서 알아보자.
시간복잡도
시간복잡도는 알고리즘이 문제를 해결하는 데 걸리는 시간을 측정하는 것
정의처럼 시간을 측정한 것이라고는 하나 시간(Time)이 아닌 일반적으로 알고리즘의 입력 크기 n에 대한 연산 횟수(Count)를 나타낸다. 따라서 시간복잡도는 알고리즘이 얼마나 효율적으로 작동하는지를 나타내는 지표가 될 수 있다.
간단한 예시를 들어보자
function sum(a, b) {
return a + b;
}위는 a와 b라는 입력값을 받아 더하는 함수이다. 이 함수는 a,b의 입력값에 변화와 상관없이 언제나 같은 시간이 걸린다. 단 한번만 계산하면 되기 때문에 O(1)의 상수 시간의 복잡도를 가진 코드이다.
그렇다면 다음 코드를 보자
function findMax(arr) {
let max = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}일정 배열을 발복문을 돌리면서 가장 큰 값을 찾아서 반환하는 함수이다. 이는 arr가 가진 배열의 인덱스의 개수(n)에 따라서 계산하는 횟수가 n번으로 달라진다. 따라서 이 함수는 O(n)의 시간복잡도를 가진다.
간단하게 생각하면 위와 같은 코드에서 for문이 1번 도는데 사용되는 시간이 n이다, 그렇다면 2중for문을 작성하게 된다면 n번과 n번으로 O(n^2)의 복잡도를 가지게 될 것이다.
공간복잡도
공간복잡도는 알고리즘이 문제를 해결하는 데 필요한 메모리 공간의 크기를 측정하는 것
알고리즘이 실행되는 동안 사용하는 메모리의 양을 나타낸다. 이는 보통 알고리즘에서 사용되는 변수, 데이터 구조, 임시 저장소 등을 고려하여 측정된다.
공간복잡도 또한 위와 같은 예시를 들어보자.
function sum(a, b) {
return a + b;
}변수가 선언된 a,b값이 가진 공간만 사용하기 때문에 O(1)이다. 그럼 두번째 예시를 보자
function findMax(arr) {
let max = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}두번째 예시의 시간복잡도는 O(n)이었다. 하지만 이 함수의 공간복잡도는 입력값arr가 들어왔을 때 결정되는 return값 max와 for문을 돌기 위한 i가 차지하는 공간 2개가 고정되어 있기 때문에 이 함수 또한 공간복잡도는 O(1)인 고정공간을 갖는다.
이처럼 같은 함수라도 시간복잡도와 공간복잡도는 다르게 적용될 수 있다.
그렇다면 공간복잡도가 O(n)이 되는 함수는 어떠한 형태를 갖게될까?
function reverse(arr) {
let result = [];
for (let i = arr.length - 1; i >= 0; i--) {
result.push(arr[i]);
}
return result;
}위 함수는 함수 내에서 새로운 배열을 생성하는 변수 result가 선언되고, 이 배열에 원래 배열 arr의 모든 요소를 역순으로 추가(push)한다. 따라서 입력 배열의 크기에 따라 result 배열의 크기가 결정되며, 이 크기는 입력 크기 n에 비례하게 된다.
정리
우리는 코드를 작성하는데 있어서 리소스를 줄이고 최대의 효율을 내기 위해서 위의 복잡도를 항상 생각하면서 코드를 작성해야 한다. 쇼핑을 할 때도 우리는 같은 물품에 대해서 가격과 배송시간 배송비등 여러가지를 생각하며 가성비를 따지듯이 코드의 작성 또한 시간복잡도와 공간복잡도를 나누어 생각하며 어느것이 가성비가 더 좋을지 생각하며 작성하도록 하자.
