들어가며
SOPT에서 프로젝트를 진행하고 있습니다. 한 번은 알고리즘을 활용한 API를 개발했습니다. 그때 제 코드를 본 동료가, 이 코드의 시간 복잡도는 얼마나 되는지 물어봤습니다. 하지만 저는 시간 복잡도라는 것 자체를 몰라서 대답할 수 없었습니다. 만약 코드의 시간 복잡도가 좋지 못하다면, 프로젝트에도 악영향을 줄 수 있다는 것을 처음 깨달았습니다. 더 늦기 전에 시간 복잡도를 반드시 공부해야겠다고 생각했습니다. 보다 더 효율적인 코드를 구성할 수 있도록 노력하고자 시간 복잡도를 공부합니다.
시간 복잡도와 Big-O(빅-오)란?
시간 복잡도는 알고리즘을 처리하는 데 얼마의 시간이 걸리는지 알려줍니다. 이런 알고리즘의 시간 복잡도는 주로 빅-오 표기법을 사용하여 나타냅니다.
Big-O(빅-오)란 알고리즘의 성능을 수학적으로 표현해주는 표기법입니다. 이를 통해 알고리즘의 시간과 공간 복잡도를 표현할 수 있습니다. 빅오 표기법은 알고리즘을 처리하는 실제 시간을 표시하는 것이 아닙니다. 빅오 표기법은 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하기 위해 사용합니다. 그렇다면 빅오 표기법의 예시에 대해 알아보겠습니다.
O(1) : Constant Time
먼저 O(1)입니다. 입력 데이터의 크기에 상관없이 일정한 시간이 걸리는 알고리즘을 O(1)이라 말합니다.
const example = [1,2,3,4,5];
function findO1(example) {
console.log(example[0]); // O(1)
console.log(example[1]); // O(1)
}
findO1(example);
지금 example 배열 안에는 5개의 element가 있습니다. 하지만 만약 element가 무수히 많더라도, findO1 함수는 배열의 첫 번째와 두 번째 element만을 찾고 있습니다. 이 작업은 단 한 번만 이루어지면 됩니다. 이런 경우 알고리즘을 O(1)의 시간 복잡도를 가진다라고 표현합니다.
O(n) : Linear Time
그다음, O(n)입니다. O(n)은 입력 데이터의 크기에 비례해서 처리시간도 늘어나는 알고리즘을 표현할 때 사용합니다.
const people = ['epitone', 'junggyun', 'sangsu', 'soonhee', 'hansik'];
const findPerson = array => {
for (let i = 0; i < array.length; i++) {
if (array[i] === 'hansik') {
console.log("Found hansik");
}
}
};
findPerson(people);
만약 findPerson() 함수의 Big-O을 계산해보겠습니다. 먼저 people 배열의 길이가 5입니다. 그래서 findPerson 안의 반복문은 총 5번 동작합니다. 만약 people 배열의 길이가 늘어나면 늘어날수록, 반복문이 동작하는 횟수는 비례해서 증가합니다. 즉, 데이터가 증가함에 따라 비례해서 처리시간도 같이 증가합니다. 언제나 데이터와 시간이 같은 비율로 증가하기 때문에 그래프는 직선으로 표기됩니다.
O(n^2) : Quadratic Time
입력 데이터의 크기의 제곱만큼 처리시간이 걸리는 알고리즘을 표현할 때 사용합니다.
const people = ["epitone", "junggyun", "sangsu", "soonhee", "hansik"];
const findPerson = (array) => {
for (let i = 0; i < array.length; i++) {
for (let k = 0; k < array.length; k++) {
console.log(array[i], array[k]);
}
}
};
findPerson(people);
for문 안에 for문을 활용해서, 원하는 데이터를 구하는 함수입니다. 만약 people 배열의 크기가 늘어날수록, 반복하는 횟수가 비례해서 늘어납니다. O(n)보다 시간 복잡도가 훨씬 늘어날 수 있는 부분을 생각할 수 있습니다. 배열의 길이가 크지 않다면, 당장은 부담이 없을 수 있지만, 배열의 길이가 늘어날 때마다 처리시간의 부담이 더 커집니다.
O(2^n)
피보나치수열을 표현한다면, O(2^n)을 표현할 수 있습니다.
피보나치수열은 아래와 같은 그림으로 표현됩니다. 그렇다면, 피보나치의 수열은 어떻게 코드로 구현할 수 있을까요?
function a(n){
if(n <= 0) {
return 0;
} else if(n === 1) {
return 1;
}
return a(n-1) + a(n-2);
}
피보나치수열을 구하는 코드를 재귀 함수를 통해 구현한다면 이렇게 표현할 수 있습니다.
즉 함수를 호출할 때마다 바로 전 숫자와 그 전 숫자를 알아야 숫자를 더하면서 앞으로 나올 숫자를 파악할 수 있습니다. 이렇게 매번 함수가 호출될 때마다 두 번씩 호출합니다. 이걸 트리의 높이만큼 반복합니다.
n의 제곱보다도 데이터의 증가에 따라 처리량이 현저하게 늘어나는 그래프를 볼 수 있습니다.
O(log n)
이진 탐색 등의 알고리즘을 표현할 때 사용합니다.
let arr = [];
function log(k, s, e){
for(let i = s; i <= e; i++){
arr.push(i);
let m = (s+e)/2;
if(arr[m] === k){
console.log(m)
} else if(arr[m]> k){
return log(k, s, m-1);
} else{
return log(k, m+1,e)
}
}
}
대표적인 알고리즘은 이진 검색입니다. 만약 정렬된 배열에서 특정 숫자를 찾을 때, 이진 검색을 이용한다면 배열의 가운데 값과 키값을 비교합니다. 만약 배열의 가운데 값이 키값보다 작다면, 키값보다 작은 값들은 볼 필요가 없습니다. 그럼 다시 없어진 배열 값을 제외한 elements들 중에서도 중간값을 찾아서 키값과 비교합니다. 이렇게 한번 처리할 때마다 검색해야 하는 데이터의 양이 절반씩 떨어지는 알고리즘을 O(log n) 알고리즘이라 합니다.
이와 같은 방법을 활용한다면, 수많은 데이터가 존재해도 성능은 크게 차이 나지 않습니다.
Drop Constants
Big-O 표기법을 활용하면 다양한 경우의 수를 살펴볼 수 있습니다. 하지만 Big-O 표기법에서는 상수값을 과감히 버려야 합니다.
const example = [1,2,3,4,5];
function findO1(example) {
console.log(example[0]); // O(1)
console.log(example[1]); // O(1)
}
findO1(example);
O(1) 표기법에서 활용했던 함수를 다시 가져왔습니다.
만약 findO1의 함수를 실행한다면, 시간 복잡도는 O(2)가 될 것입니다. 하지만 Big-O 표기법에서는 그냥 O(1)로 표기합니다. Big-O 표기법은 실제 알고리즘의 러닝타임을 구하기 위해 만드는 것이 아닙니다. Big-O 표기법은 장기적으로 데이터가 증가한다면, 처리시간의 증가율은 얼마나 될 것인지를 예측하기 위해 만들어진 것입니다. 이 때문에 상수값은 고정된 숫자이기에 증가율에도 고정된 상수만큼의 영향을 미치게 됩니다. 즉, Big-O 표기법에서는 증가하지 않는 숫자는 신경 쓰지 않습니다.
Big-O 계산 규칙
Big-O의 계산은 4가지 규칙을 따릅니다. 가장 먼저 소개드릴 규칙은 Worst Case 규칙입니다.
Big-O Rule 1 : Worst Case
Big-O를 계산할 때는 항상 최악의 상황을 고려해야 합니다.
const people = ["epitone", "junggyun", "hansik", "sangsu", "soonhee"];
const findPerson = (array) => {
for (let i = 0; i < array.length; i++) {
if (array[i] === "hansik") {
console.log("Found hansik");
}
}
};
findPerson(people);
만약 이 코드를 봤을 때, people의 배열 element가 5개이기 때문에 한식을 찾기 위해서 이 함수는 5번의 작업이 필요합니다. 한식은 3번째에 위치하고 있음에도 5번을 작업하고 있습니다.
const people = ["epitone", "junggyun", "hansik", "sangsu", "soonhee"];
const findPerson = (array) => {
for (let i = 0; i < array.length; i++) {
if (array[i] === "hansik") {
return console.log("Found hansik");
}
}
};
findPerson(people);
간단하게 조건에 맞는 값을 찾는다면, return 해주면 실행을 중지하기 때문에 더 효율적인 코드가 됩니다. 하지만 코드의 효율이 좋아지더라도 Big-O를 계산할 때에는 큰 의미는 없습니다. 왜냐면 Worst Case를 고려해야 하기 때문입니다.
이 경우 Worst Case는 길이가 5인 배열에서 한식이 맨 마지막 element에 있는 경우입니다. 이 경우 아무리 한식을 찾자마자 return 한다고 해도 한식이 맨 마지막에 있기 때문에 결국에는 5번을 반복 실행할 수밖에 없습니다.
만약 이런 최악의 상황을 고려했을 때, element의 개수가 증가한다면 작업 횟수도 정비례하게 증가하게 됩니다. 이 때문에 위 경우는 O(n), Linear Time이 됩니다.
Big-O Rule 2 : Remove Constants
Big-O를 계산할 때는 상수를 제거하라는 의미입니다.
function printItems(items) {
console.log(items[0]); // O(1)
let middleIndex = Math.floor(items.length / 2);
let index = 0;
while (index < middleIndex) { // O(n/2)
console.log(items[index]);
index++;
}
for (let i = 0; i < 100; i++) { // O(100)
console.log('hi');
}
}
위 코드의 Big-O를 계산하면 O(1 + n/2 + 100)이 됩니다. 하지만 만약 Items 배열의 길이(n)가 1억이라면 어떻게 될까요? 이 경우 1억에 1을 더하든, 100을 더하든, 1억을 2로 나누는 상황은 크게 달라지지 않을 것입니다. 결국 이 경우에도 Big-O는 O(n), Linear Time입니다. 따라서 상수는 제거하고, O(n)으로 표기해야 합니다.
function compareBoxes(boxes) {
boxes.forEach(function(boxes) { // O(n)
console.log(boxes);
});
boxes.forEach(function(boxes) { // O(n)
console.log(boxes);
});
}
위도 마찬가지로 O(n)이 두 번 반복되므로 O(2n)이지만, 상수는 버리기 때문에 O(n)입니다. Big-O 계산은 정확한 속도를 계산하려고 하는 것이 아니라는 것을 다시금 생각해봐야 합니다.
Big-O Rule 3 : Different Terms for Inputs
function compareBoxes(boxes, boxes2) {
boxes.forEach(function(boxes) { // O(a)
console.log(boxes);
});
boxes2.forEach(function(boxes2) { // O(b)
console.log(boxes);
});
}
이 코드의 경우 함수의 인자 값이 서로 다릅니다. 첫 번째 인자 값이 boxes이고, 두 번째 인자 값이 boxes2이기 때문에 각 인자의 크기에 따라 작업 횟수가 달라집니다. 인자 값이 다를 경우에는 따로 계산을 해줘야 하기 때문에 이 경우 Big-O는 O(a+b)입니다.
Big-O Rule 4 : Drop Non Dominants
function printAllNumber(numbers) {
numbers.forEach(function(number) { // O(n)
console.log(number);
});
numbers.forEach(function(firstNumber) {
numbers.forEach(function(secondNumber) {
console.log(firstNumber + secondNumber); // O(n^2)
});
});
}
printAllNumber([1,2,3,4,5]);
위의 함수 코드의 경우 O(n + n^2)입니다. 하지만 numbers 배열의 길이가 커질수록 n^2의 작업 횟수가 극적으로 증가하기 때문에 이도 결국엔 O(n^2), Quadratic Time이 됩니다.
공간 복잡도(Space Complexity)
시간 복잡도가 input 되는 element의 증가에 따른 작업 횟수의 증가를 보는 것이었습니다. 하지만 시간 복잡도와는 다르게 공간 복잡도는 작업 수행 시 공간을 얼마나 추가로 사용하게 되는지를 봅니다. 즉, 알고리즘에 사용되는 메모리의 양을 공간 복잡도라고 합니다.
만약 효율적인 알고리즘을 사용한다고 가정했을때 일반적으로 시간과 공간은 반비례 관계입니다. 좋은 알고리즘을 비교할 땐 시간이 빠른 경우엔 공간을 많이 사용하고, 시간이 느린 경우엔 공간을 적게 쓰는 경우가 있습니다.
공간 복잡도에 영향을 미치는 요소
공간 복잡도에 영향을 미치는 요소는 변수, 자료구조(Data Structure), 함수 호출(Function Call), 할당(Allocation) 네 가지입니다.
function booo(n) {
for (let i = 0; i < n.length; i++) {
console.log('booo!');
}
}
booo([1,2,3,4,5]);
공간 복잡도를 계산할 때는 특정 작업 내에서 메모리 공간을 얼마나 많이 사용하는지를 봅니다. 위 코드는 함수 내에서 변수 i를 0이라고 선언한 것 외에는 공간 복잡도에 영향을 미치는 다른 작업이 없기 때문에 이 경우 공간 복잡도는 O(1)입니다. 즉 공간 복잡도에서는 input이 얼마나 큰지는 중요한 부분이 아닙니다.
function arrayOfHiNTimes(n) {
let hiArray = [];
for (let i = 0; i < n; i++) {
hiArray[i]='hi';
}
return hiArray;
}
arrayOfHiNTimes(6); // O(n)
위의 코드의 공간 복잡도는 O(n)입니다. for문 내에서 변수 선언이 6번 반복적으로 실행되면서 공간을 6번 사용했기 때문입니다. 공간 복잡도도 다양한 부분을 생각할 수 있기 때문에 앞으로 여유가 된다면 더 공부하고 싶습니다.
Big-O 그래프
Big-O의 그래프를 보면, 처리해야 할 데이터가 늘어날수록 데이터를 처리하는 속도가 어떻게 변하는지를 볼 수 있는 그래프입니다. O(1)에서부터 O(n!)까지 다양한 Big-O 표기법이 존재합니다. 만약 알고리즘을 생각하신다면, 시간 복잡도는 얼마나 되는지를 항상 생각하면서 코드를 구성해보시는 것은 어떨까요.
마치며
자료구조별로 시간 복잡도가 어떻게 되는지를 한눈에 볼 수 있는 표입니다. 저도 어떤 자료구조를 어떻게 활용했을 때, 시간 복잡도를 줄일 수 있는지를 항상 생각해보면서 코드를 구성하고 싶습니다. 자료구조를 계속 공부하면서 시간 복잡도에 대한 고민을 끝없이 하고 싶습니다.
참고
(Algorithm) 시간의 복잡도
안녕하세요. 이번 시간에는 시간의 복잡도를 설명하겠습니다. 시간의 복잡도는 알고리즘을 수행하는 데 평균적으로, 또는 최악의 경우 얼마만큼의 시간이 걸리는 지 보여줍니다. 반대의 개념으
www.zerocho.com
자바스크립트에서 Big O(시간 복잡도)란?
*Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다. *https://soldonii.github.io에서 2019년 8월 19일(월)에 작성한 글을 티스토리로 옮겨..
soldonii.tistory.com
시간 복잡도 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 계산 복잡도 이론에서 시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다. 컴퓨터과학에서 알고리
ko.wikipedia.org
피보나치 수 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 피보나치 수를 이용한 사각형 채우기 수학에서, 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다.
ko.wikipedia.org
'자료구조' 카테고리의 다른 글
| [자료구조] 스택 with JavaScript (0) | 2021.11.07 |
|---|---|
| [자료구조] 해시테이블 with JavaScript (1) | 2021.10.31 |
| [자료구조] 연결리스트 with JavaScript (2) | 2021.09.25 |
