들어가며
Big-O 표기법은 알고리즘의 성능과 효율성을 나타내기 위한 표기법입니다.
Big-O 표기법은 알고리즘의 성능을 이해하고 최적화하는 데 도움을 주며, 특히 데이터의 양이 많아질수록 그 중요성이 더욱 부각됩니다.
이번 글에서는 Big-O 표기법의 정의, Big-O 표기법의 중요성, Big-O 표기법 종류와 예시, JavaScript 주요 배열 메서드의 시간복잡도에 대해 자세히 살펴보겠습니다.
Big-O 표기법이란?
Big-O 표기법은 알고리즘의 시간 복잡도와 공간 복잡도를 예측하는 수학적 표기법입니다.
이는 알고리즘이 처리해야 할 데이터의 양이 증가할 때, 알고리즘의 실행 시간이 어떻게 변하는지를 설명합니다. (예를 들어 n 값 (인풋 값)이 증가함에 따른 알고리즘의 처리 시간이 어떻게 변하는지를 설명합니다.)
Big-O 표기법은 점근 표기법 중 하나이며 일반적으로 상수와 계수를 제거하고 알고리즘의 복잡도를 단순화하여 나타내며, 연산 횟수 계산법을 하나의 약속된 형식으로 만들어주며 알고리즘의 인풋 값이 증가함에 따라서 연산처리시간이 어떻게 함께 증가하는지에 대해 설명할 수 있게 해줍니다.
정리해 보자면 Big-O 표기법은 즉 알고리즘의 직접적인 모든 연산 횟수를 계산하는 것이 아니라(처리하는 실제 시간을 표시하는 것이 아님.) 인풋의 증가에 따른 연산 처리시간의 증가율을 예측하는 척도라고 할 수 있습니다.
Big-O 표기법의 중요성
알고리즘의 효율성을 평가하는 것은 소프트웨어 개발에서 매우 중요합니다.
특히 대규모 데이터 처리나 실시간 시스템에서는 알고리즘의 성능이 전체 시스템의 성능에 큰 영향을 미칠 수 있습니다. 따라서 Big-O 표기법을 통해 알고리즘의 성능을 정량적으로 분석하고, 최적의 알고리즘을 선택하는 것이 필수적이며 이는 특히 이는 특히 대규모 데이터 처리나 실시간 시스템에서 매우 중요합니다.
Big-O 표기법의 종류
1. 상수 시간 복잡도 (Constant Time)
 |
입력 데이터의 크기와 관계없이 실행 시간이 일정합니다. 즉 인풋 크기와 상관없이 항상 일정한 시간 소요되며 인풋 데이터가 증가해도 성능에는 영향을 미치지 않습니다. 해시테이블 또는 배열에서 인덱스로 값을 읽어올 때 상수 시간으로 처리됩니다. |
예시)
function constantTime (arr){
return arr[0];
}
2. 로그 시간 복잡도 (Logarithmic)
 |
데이터의 크기가 증가할 때, 실행 시간은 로그에 비례하여 증가합니다. 즉 인풋의 크기가 늘어나더라도 처리시간이 로그만큼 짧아지는 시간 복잡도입니다.
|
예시)
function logarithmic(n) {
let count = 0 ;
for (let i = 2; i <= n; i *= 2){
count++;
}
return count;
};
// logarithmic(16) //4
3. 선형 시간 복잡도(Linear Time)
 |
데이터의 크기가 증가할 때, 실행 시간도 비례하여 증가합니다. 즉 인풋의 값과 연산 수행 횟수가 1 대 1의 관계를 갖는 시간 복잡도입니다. 입력값과 비례한 성능을 가지고 있는 시간 복잡도이며 순차 탐색이 선형 시간 복잡도에 대표적 알고리즘에 해당합니다. |
예시)
function linearTime(str) {
let count = 0;
for (let i = 0; i < str.length; i++) {
count++;
}
return count;
}
4. 선형 로그 시간 복잡도 (Linear Logarithmic Time)
 |
데이터 크기가 선형적으로 증가하면 실행 시간은 로그 값에 비례하여 증가합니다. 입력값이 늘어나면 실행 시간은 O(n log(n))형태로 증가하게 되며, 이는 성능을 비교적 효율적으로 유지할 수 있게 해주지만 입력 크기가 매우 커질 경우, 여전히 실행 시간이 급격히 늘어날 수 있습니다. 즉 데이터의 크기가 증가할 때 실행 시간은 선형적으로 증가하면서도 로그의 영향을 받아 그 증가 속도가 다소 완만해지는 시간 복잡도이며 병합 정렬과 퀵 정렬 등이 대표적 알고리즘에 해당합니다. |
예시)
function linearLogarithmicTime (arr) {
let count = 0;
for (let i = 0; i < arr.length; i++) {
for (let j = 1; j < arr.length; j*=2) {
count += 1;
console.log(count);
}
}
}
5. 이차 시간 복잡도 (Quadratic Time)
 |
데이터의 크기가 증가할 때, 실행 시간은 제곱에 비례하여 증가합니다. 즉 인풋 값 증가 시 시간이 n의 제곱 비율로 증가하는 시간 복잡도로 데이터가 많아질수록 연산 수행 횟수가 제곱에 비례하여 늘어나는 시간 복잡도입니다. 보통 반복문 2개가 중첩되는 케이스가 여기에 해당되며 (n이 10일 경우 100회의 연산이 실행됨) 버블 정렬, 삽입 정렬 등이 대표적인 알고리즘에 해당합니다.
|
예시)
function quadraticTime(arr) {
let count = [];
for (let i = 0; i < arr.length; i++) {
count[i] = [];
for (let j = 0; j < arr.length; j++) {
count[i].push(arr[j]);
}
}
return count;
}
6. 지수 시간 복잡도 (Exponential Time)
 |
데이터의 크기가 증가할 때 실행 시간은 기하급수적으로 증가합니다. 지수 시간 복잡도를 가진 알고리즘은 일반적으로 비효율적이며 예를 들어 피노나치 수열의 계산 등이 있습니다. |
예시)
function fibonacci(num) {
if (num <= 1) return 1;
return fibonacci(num - 1) + fibonacci(num - 2);
}
7. 팩토리얼 시간 복잡도 (Factorial Time)
 |
그래프가 거의 수직에 가까운 매우 느린 성능의 비효율적인 시간 복잡도로 O(n!)로 표현되며, 이는 알고리즘의 실행 시간이 입력 크기 n에 대해 팩토리얼로 증가함을 의미합니다. n이 주어졌을 때 n!=n×(n−1)×(n−2)×…×1n!=n×(n−1)×(n−2)×…×1로 정의됩니다. (만약 n이 10이라면 약 360만번의 연산이 요구)
|
예시)
function factorial(n) {
let num = n;
if (n === 0) return 1;
for (let i = 0; i < n; i++) {
num - n * factorial(n - 1);
}
return num;
}
요약
| 증가 함수 | 특징 | 알고리즘 |
| O(1) | 입력 데이터의 크기와 관계없이 실행 시간이 일정 | 해시 테이블 |
| O(log n) | 데이터의 크기가 증가할 때, 실행 시간은 로그에 비례하여 증가 | 이진 탐색 |
| O(n) |
데이터의 크기가 증가할 때, 실행 시간도 비례하여 증가 선형 시간 복잡도를 기준으로 이보다 느린 알고리즘들을 비효율적으로 본다. 인풋의 모든 값을 적어도 한번한번씩을 확인하는 알고리즘들에 주로 사용 |
순차 탐색 |
| O(n log n) | 데이터 크기가 선형적으로 증가하면 실행 시간은 로그 값에 비례하여 증가 | 병합 정렬, 퀵 정렬 |
| O(n²) | 데이터의 크기가 증가할 때, 실행 시간은 제곱에 비례하여 증가 | 버블정렬, 삽입 정렬 |
| O(2ⁿ) | 데이터의 크기가 증가할 때 실행 시간은 기하급수적으로 증가 | |
| O(n!) |
그래프가 거의 수직에 가까운 매우 느린 성능 팩토리얼 시간 복잡도는 알고리즘의 효율성을 크게 저하시킴. 따라서, 이러한 복잡도를 가진 알고리즘은 입력 크기가 작을 때만 사용해야 함. |
javascript에서 사용되는 주요 배열 메서드의 시간 복잡도
| 증가 함수 | 메서드 |
| O(1) | push() , pop() |
| O(n) | shift(), unshift(), concat(), splice(), slice(), indexOf(), findIndex(), forEach(), map(), filter(), reduce(), fill() , filter() , find() , reverse() , slice(), some(), toLocaleString(), toString() |
| O(n log n) | sort() |
마치며
이번 글에서는 Big-O 표기법과 JavaScript 배열 메서드의 시간 복잡도에 대해 살펴보았습니다.
알고리즘의 성능을 분석하고 비교하는 데 있어 Big-O 표기법은 필수적인 도구입니다. 입력 크기가 증가함에 따라 알고리즘의 실행 시간이 어떻게 변화하는지를 명확하게 나타내 주기 때문에, 개발자들에게 최적화와 더욱 효율적인 알고리즘과 더 나은 방법을 찾는데 큰 도움을 줍니다.
Big-O 표기법을 이해함으로써, 개발자들은 각 알고리즘의 장단점을 비교할 수 있으며, 문제 해결을 위한 더 나은 전략을 세울 수 있습니다. 특히, 대규모 데이터 처리나 복잡한 문제를 해결할 때, 효율적인 알고리즘 선택은 성능에 큰 영향을 미치기 때문에 더 나은 성능을 가진 프로그램을 개발하기 위해서는 항상 시간 복잡도와 Big-O 표기법을 염두에 두면서 개발한다면 더 나은 사용자 경험 제공, 더 효과적인 개발을 할 수 있을 거라 생각됩니다.
감사합니다.