복잡도 ?
복잡도의 '복잡'이란 의미는 계산 복잡도에서 나온 단어로 좀 더 값이 크게 증가하는 정도를 의미한다.
즉 , 코드의 복잡성보다 수치적으로 값이 얼마나 더 큰지에 대해 초점을 맞춰야 한다.
시간 복잡도 (Time Complexity)
- 작업을 수행하는 데 걸리는 시간이 입력 크기에 따라 어떻게 증가하는지를 나타내는 것
- 어떠한 알고리즘이 있는데, 이 알고리즘이 문제를 해결하기 위한 시간(연산)의 횟수
즉, 알고리즘이 수행되는데 소요되는 연산 횟수를 이야기 - 알고리즘이 입력 크기에 따라 실행되는 데 걸리는 시간의 증가율을 설명하는 개념으로써,
이는 일반적으로 알고리즘의 성능을 평가하는 데 사용 - 동일한 기능을 수행하는 알고리즘들이 있다면, 이들 사이에서 복잡도가 낮을수록 성능이 우수 = 좋은 알고리즘
↓ 시간 복잡도 이해를 돕는 예시
가령, 한 명의 사람이 전화번호부에서 특정 번호를 찾는 경우를 생각해봅시다.
- 만약 전화번호부의 크기가 100개의 번호라면, 찾는데 걸리는 시간은 상대적으로 빠를 것입니다.
- 하지만 전화번호부의 크기가 1000개, 10000개로 커진다면, 번호를 찾는 데 걸리는 시간도 함께 더 많아질 것입니다.
시간 복잡도를 이해하는 것은 알고리즘을 선택할 때 어떤 것이 효율적이고 빠른지를 이해하는 데 도움이 됩니다.
이는 특히 큰 규모의 데이터나 문제를 다룰 때 중요합니다.
*알고리즘(algorithm) 이란?
특정 문제를 효율적이고 빠르게 해결하는 것이 궁극적인 목표로 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것
시간 복잡도를 사용하는 이유
- 알고리즘의 성능 비교 : 서로 다른 알고리즘 가능 성능을 비교 가능
- 문제 해결 시간 예측 : 알고리즘의 실행 시간이 입력 크기에 어떻게 의존하는지 파악 가능
- 최적화 : 알고리즘의 실행 시간이 빠르게 증가하는 부분을 찾아 개선하거나, 더 효율적인 알고리즘으로 교체하여 성능향상 가능
- 자원 관리 : 시간 복잡도가 낮은 알고리즘을 선택하면 자원을 효율적으로 활용 가능
Big-O Notation
빅오 표기법 | 시간 복잡도 표기법
Big-O
알고리즘의 시간 복잡도를 간결하게 나타내는 표기법
알고리즘 성능을 이해하고 예측하는 데 매우 유용
- 알고리즘의 실행 시간이 입력 크기에 따라 어떻게 증가하는지를 설명가능하며, 이를 통해 알고리즘의 성능을 비교하고, 어떤 입력에 대해 더 효율적인 알고리즘을 선택할 수 있다.
- 빅오 표기법은 O(f(n))으로 표현되며, O는 "알고리즘의 최악의 경우 시간 복잡도" 즉, 해당 함수의 상한을 의미하고 f(n)은 입력 크기 n에 따라 알고리즘이 필요로 하는 계산량을 나타내는 함수이다. 따라서 O(f(n))은 입력 크기 n에 따른 함수 f(n)의 상한을 나타낸다. *수학적인 표기법에서 f(n)은 함수를 나타내기 위한 표기법
Big-O 그래프(Graph)
input되는 element의 양이 많아질수록 작업량(operation)이 얼마나 늘어나는지를 나타내는 그래프
즉, 처리해야 할 데이터가 늘어날수록 데이터를 처리하는 속도가 어떻게 변하는지를 알 수 있다.
👉성능 빠른순 O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(∞) 성능 느린순
O(1) : 상수 시간 (Constant Time)
입력데이터의 크기에 관계없이 실행 시간 일정
*배열의 끝에 요소를 추가하거나 제거하는 등의 작업들
function constantTime() {
console.log("Hello, World!");
}
constantTime(); // 실행 시간은 상수입니다.
O(log n) : 로그 시간 (log Time)
입력데이터의 크기가 로그에 비례하여 실행 시간 증가
*대표적 알고리즘: 이진 검색(Binary search)
function logarithmicTime(n) {
let i = 1;
while (i < n) {
console.log(i);
i *= 2;
}
}
logarithmicTime(8); // 입력 크기에 따라 반복 횟수가 로그적으로 증가합니다.
O(n) : 선형 시간 (linear Time)
입력데이터의 크기에 비례하여 실행 시간 증가
*배열의 모든 요소를 순회하는 작업들
function linearTime(n) {
for (let i = 0; i < n; i++) {
console.log(i);
}
}
linearTime(5); // 입력 크기에 비례하여 실행 시간이 증가합니다.
O(n log n) : 선형 로그 시간 (long linear Time)
입력데이터의 크기에 따라 걸리는 시간이 곱셈에 비례하여 시간 증가
*대표적 알고리즘: 병합정렬(Merge Sort), 퀵 정렬(Quick Sort)
function linearLogarithmicTime(n) {
for (let i = 0; i < n; i++) {
for (let j = 1; j < n; j++) {
console.log(i * j);
}
}
}
linearLogarithmicTime(5); // 입력 크기에 따라 이중 반복문이 실행됩니다.
O(n²) : 2차 시간 (quadratic Time)
이차 시간 알고리즘이라고도 불리우며, 입력데이터의 크기에 따라 걸리는 시간이 제곱에 비례하여 시간 증가
*대표적 알고리즘: 버블정렬(Bubble Sort), 삽입 정렬(Insertion Sort)
function quadraticTime(n) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
console.log(i * j);
}
}
}
quadraticTime(3); // 입력 크기의 제곱에 비례하여 실행 시간이 증가합니다.
O(n³) : 3차 시간 (cubic Time)
3차 시간 알고리즘이라고도 불리우며, 입력데이터의 크기에 따라 걸리는 시간이 거듭제곱에 비례하여 시간 증가
*대표적 알고리즘: 행렬 곱셈(Matrix Multiplication)
function cubicTime(n) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
for (let k = 0; k < n; k++) {
console.log(i * j * k);
}
}
}
}
cubicTime(2); // 입력 크기의 세제곱에 비례하여 실행 시간이 증가합니다.
O(2ⁿ) : 지수 시간 (exponential Time)
입력데이터의 크기에 따라 걸리는 시간이 지수에 비례하여 시간 증가
*대표적 알고리즘: 부분 집합 생성(Subsets Generation)
function exponentialTime(n) {
if (n <= 1) {
return n;
} else {
return exponentialTime(n - 1) + exponentialTime(n - 2);
}
}
console.log(exponentialTime(5)); // 피보나치 수열과 같은 지수적으로 증가하는 연산이 있습니다.
O(n!) : 계승 시간 (factorial Time)
입력데이터의 크기가 계승에 비례하여 실행 시간 증가
*대표적 알고리즘: 피보나치 수열(Fibonacci Sequence)
function factorialTime(n) {
if (n === 0) {
return 1;
} else {
return n * factorialTime(n - 1);
}
}
console.log(factorialTime(4)); // 팩토리얼 연산에 비례하여 실행 시간이 급격하게 증가합니다.
O(∞) : 무한 시간 (infinity Time)
종료되지 않는 무한 반복
function infiniteTime() {
while (true) {
console.log("Infinite loop!");
}
}
infiniteTime(); // 이 함수는 무한 루프에 빠져서 종료되지 않습니다.
⚠️시간 복잡도를 표기할 시 고려사항 or 단점
- 상수항 무시 : 알고리즘의 실행 시간이 입력 크기에 따라 증가하는 경향을 이해하기 위하여 빅오 표기법은 상수항을 무시한다. 그렇기에 가장 큰 영향을 미치는 항에 집중하여 알고리즘의 성능을 평가한다.
- 가장 큰 항을 제외하고 무시 : 알고리즘의 실행 시간에 가장 큰 영향을 미치는 항만을 고려하고 나머지 부분을 무시한다. 이는 알고리즘의 실행 시간이 입력 크기에 따라 가장 큰 영향을 미치는 항에 의해 결정되기 때문이다.
시간 복잡도를 평가하고 분석하는 데 사용되는 기본적인 4가지 법칙
이러한 법칙은 알고리즘의 성능을 평가하고 예측하는 데 사용하며,
입력 크기에 따른 실행 시간의 증가율을 이해하고 예상할 수 있고 알고리즘의 최적화와 선택에 도움을 준다.
| 계수 법칙 (Coefficient Law) | 상수항 형태로 표기되는 경우 예) O(2n)은 O(n)으로 표기 |
| 합의 법칙 (Sum Law) | 합 형태로 표기되는 경우. 예) O(n) + O(n²)은 O(n + n²)으로 표기 |
| 곱의 법칙 (Product Law) | 곱 형태로 표기되는 경우. 예) O(n) * O(log n)은 O(n log n)으로 표기 |
| 다항 법칙 (Polynomial Law) | 다항식 형태로 표기되는 경우 예) O(n² + n)은 O(n²)으로 표기 |
시간 복잡도의 기본적인 4가지 법칙을 알면 좋은점
- 알고리즘 이해의 용이성 : 알고리즘의 시간 복잡도를 훨씬 더 직관적으로 파악할 수 있다.
- 알고리즘 비교의 편의성 : 알고리즘들 간의 성능을 명확하게 비교할 수 있다.
- 알고리즘 설계의 지침 : 각각의 법칙을 고려하여 알고리즘을 구성함으로써 효율적인 방향으로 설계할 수 있다.
- 알고리즘 최적화의 방향성 : 각각의 법칙을 고려하여 최적화 작업을 수행함으로써 알고리즘의 성능을 향상시킬 수 있다.
Big-0 계산의 4가지 규칙
- Rule 1 : Worst Case; *최악의 경우
- Big-O를 계산할 때는 항상 알고리즘의 최악의 경우를 고려하라 - Rule 2 : Remove Constants; *상수 제거
- Big-O를 계산할 때는 상수를 무시(제거)하라 - Rule 3 : Different terms for inputs; *입력에 대한 다른 항
- Big-O를 계산할 때는 다양한 입력 크기에 따른 다른 항을 고려하라 - Rule 4 : Drop Non Dominants; *비지배적인 항 제거
- Big-O를 계산할 때는 가장 큰 영향을 주는 항 외에는 제거하라
Rule 1 : Worst Case
알고리즘이 최악의 경우에 얼마나 많은 시간이 걸리는지를 고려해야 합니다.
// 최악의 경우 시간 복잡도가 O(n)인 선형 탐색 알고리즘 예제
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) { // 배열의 길이만큼 반복
if (arr[i] === target) { // 배열 요소를 하나씩 확인하여 목표와 일치하는지 확인
return i; // 일치하는 요소의 인덱스를 반환
}
}
return -1; // 목표를 찾지 못한 경우 -1 반환
}
Rule 2 : Remove Constants
Big-O를 계산할 때는 상수를 무시하며, 항상 가장 큰 영향을 미치는 항을 고려해야 합니다.
// 상수 시간 복잡도가 O(1)인 예제
function add(a, b) {
return a + b; // 두 숫자를 더하는 작업은 상수 시간이 소요됨
}
Rule 3 : Different terms for inputs
Big-O를 계산할 때는 다양한 입력 크기에 따른 다른 항을 고려해야 합니다.
// 다양한 입력 크기에 대한 다른 항을 고려한 예제
function findMax(arr1, arr2) {
let max1 = Math.max(...arr1); // 첫 번째 배열의 최댓값을 찾는데 O(n) 시간이 소요됨
let max2 = Math.max(...arr2); // 두 번째 배열의 최댓값을 찾는데 O(m) 시간이 소요됨
return Math.max(max1, max2); // 두 최댓값 중 더 큰 값을 찾는데는 상수 시간이 소요됨
}
Rule 4 : Drop Non Dominants
Big-O를 계산할 때는 가장 큰 영향을 주는 항 외에는 제거합니다.
// 비지배적인 항을 제거한 예제
function exampleFunc(n) {
for (let i = 0; i < n; i++) { // n번 반복하므로 O(n) 시간이 소요됨
console.log(i); // 각 반복마다 상수 시간이 소요됨
}
for (let j = 0; j < n * n; j++) { // n^2번 반복하므로 O(n^2) 시간이 소요됨
console.log(j); // 각 반복마다 상수 시간이 소요됨
}
}
JavaScript에서 코드 성능을 측정하는 3가지 방법
| 종류 | 장점 | 단점 |
| console.time, console.timeEnd | 1. 가장 편리한 방법 2. 간단한 코드 작성 3. 개발자 도구의 성능 패널에서 확인가능 |
1. 브라우저 환경의 종속성이 있어 다른 실행 환경에서는 사용 불가능하기에 특정 실행 환경에서만 사용될 때, 사용 권장 2. 실행 시간이 매우 짧거나 긴 경우, 콘솔에 출력이 잘릴 수 있음 |
| Date | 1. 일반적이고 널리 사용되는 방법 2. 간단한 코드 작성 가능 및 가독성 좋음 3. 보통 수준의 충분한 정확도 |
1. 여러번 반복 실행하거나 정밀한 측정이 필요 할 때, 성능에 약간의 오버헤드 발생 |
| performance.now | 1. 브라우저에서 사용하는 표준 방법 2. 더 높은 수준의 정밀도를 제공 |
1. 복잡한 코드를 작성할 가능성 우려 2. 브라우저 환경에서만 사용 가능 3. window.performance.now()이므로 Node.js에서는 별도의 호출이 필요 |
1. console.time(), console.timeEnd() 함수를 이용한 코드 성능측정 방법
console.time("execution");
// 실행할 코드...
console.timeEnd("execution");
1-1. console.time(), console.timeEnd() 함수를 이용한 코드 성능측정 방법_예제.1
console.time("execution");
let total = 0;
for (let i = 0; i < 100000000; i++) {
total += i;
}
console.timeEnd("execution"); // execution: 100.123ms
2. Date 객체를 이용한 코드 성능측정 방법
const start = new Date().getTime();
// 실행할 코드...
const end = new Date().getTime();
console.log(end - start);
2-1. Date 객체를 이용한 코드 성능측정 방법_예제.1
const start = new Date().getTime(); // 실행 시작 시간 기록
const N = 100000000;
let total = 0;
for (let i = 0; i < N; i += 1) {
total += i; // 0부터 N까지의 합 계산
}
const end = new Date().getTime(); // 실행 종료 시간 기록
console.log(end - start); // 실행 시간 출력 (밀리초 단위)
3. performance.now() 메서드를 이용한 코드 성능측정 방법
const start = performance.now();
// 실행할 코드...
const end = performance.now();
console.log(end - start);
3-1. performance.now() 메서드를 이용한 코드 성능측정 방법_예제.1
function exampleAlgorithm(n) {
let sum = 0;
for (let i = 0; i < n; i++) {
sum += i;
}
return sum;
}
const startTime = performance.now();
// 실행할 알고리즘 함수 호출
const result = exampleAlgorithm(1000000);
const endTime = performance.now();
const executionTime = endTime - startTime;
console.log("결과:", result); // 결과: 499999500000
console.log("실행 시간:", executionTime, "밀리초"); // 실행 시간: XXX 밀리초
함수에 따른 시간복잡도
| 시간 복잡도 | 함수명 |
| O(1) | pop(), push(), shift(), values(), with(), at(), entries(), every(), isArray(), keys(), |
| O(n) | concat(), copyWithin(), fill(), find(), findIndex(), findLast(), findLastIndex(), flat(), flatMap(), forEach(), from(), fromAsync(), group(), groupToMap(), includes(), indexOf(), join(), of(), lastIndexOf(), map(), filter(), reduce(), reduceRight(), reverse(), slice(), splice(), some(), toLocaleString(), toReversed(), toSpliced(), toString(), unshift(), |
| O(n log n), linear time on average |
sort(), toSorted(), |
참고문헌 사이트
'JavaScript' 카테고리의 다른 글
| [JS] 자료구조/알고리즘 中 스택(Stack) (0) | 2024.05.09 |
|---|---|
| [JS] 자바스크립트 reduce(리듀스) 이해하기 (0) | 2024.01.28 |
| [JS] 자바스크립트 소수점 내리기/버리기 (1) | 2024.01.08 |
| [JS] forEach 함수 | 개념이해 및 사용예제 (0) | 2023.10.17 |
