Frontend Development
시간복잡도와 공간복잡도: 개발자가 알아야 할 성능 최적화의 기초
Kun Woo Kim
2025. 7. 23. 17:16
728x90
프론트엔드 개발에서 성능은 사용자 경험을 좌우하는 핵심 요소입니다. 특히 대용량 데이터 처리, 복잡한 UI 렌더링, 실시간 검색 기능 등을 구현할 때 알고리즘의 효율성이 직접적으로 성능에 영향을 미칩니다. 이 글에서는 시간복잡도와 공간복잡도의 개념부터 실무에서의 활용 방법까지 체계적으로 정리하겠습니다.
알고리즘 복잡도란 무엇인가?
성능 평가의 필요성
실제 개발에서 동일한 기능을 구현하는 여러 가지 방법이 존재할 때, 어떤 방법이 더 효율적인지 판단해야 합니다.
// 배열에서 최댓값 찾기 - 방법 1
function findMaxMethod1(arr) {
let max = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
// 배열에서 최댓값 찾기 - 방법 2
function findMaxMethod2(arr) {
return Math.max(...arr);
}
// 배열에서 최댓값 찾기 - 방법 3
function findMaxMethod3(arr) {
return arr.sort((a, b) => b - a)[0];
}위의 세 가지 방법 모두 같은 결과를 반환하지만, 성능은 크게 다릅니다. 실행 시간을 직접 측정할 수도 있지만, 이는 다음과 같은 문제가 있습니다:
실행 시간 측정의 한계:
- 하드웨어 환경에 따라 결과가 달라짐
- 다른 프로그램의 영향을 받음
- 작은 데이터에서는 차이를 감지하기 어려움
- 매번 다른 결과가 나올 수 있음
복잡도 분석의 장점
복잡도 분석은 이러한 문제를 해결하기 위해 연산의 횟수와 메모리 사용량을 기준으로 알고리즘을 평가합니다.
주요 장점:
- 환경에 독립적인 평가
- 입력 크기가 커질 때의 성능 예측 가능
- 알고리즘 간 객관적 비교
- 병목 지점 식별 용이
시간복잡도와 공간복잡도
시간복잡도 (Time Complexity)
시간복잡도는 입력 크기 n에 대해 알고리즘이 수행하는 연산의 횟수를 나타냅니다.
// O(1) - 상수 시간
function getFirstElement(arr) {
return arr[0]; // 배열 크기와 관계없이 항상 1번의 연산
}
// O(n) - 선형 시간
function sumArray(arr) {
let sum = 0;
for (let i = 0; i < arr.length; i++) { // n번 반복
sum += arr[i];
}
return sum;
}
// O(n²) - 이차 시간
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) { // n번 반복
for (let j = 0; j < arr.length - 1; j++) { // n번 반복
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}공간복잡도 (Space Complexity)
공간복잡도는 입력 크기 n에 대해 알고리즘이 사용하는 메모리 공간을 나타냅니다.
// O(1) - 상수 공간
function reverseString(str) {
let result = '';
for (let i = str.length - 1; i >= 0; i--) {
result += str[i];
}
return result; // 입력 크기와 관계없이 고정된 메모리 사용
}
// O(n) - 선형 공간
function createArray(n) {
const arr = new Array(n); // n개의 요소를 저장할 공간 필요
for (let i = 0; i < n; i++) {
arr[i] = i;
}
return arr;
}
// O(n) - 재귀 호출 스택
function factorial(n) {
if (n <= 1) return 1;
return n * factorial(n - 1); // n번의 재귀 호출로 스택에 n개의 프레임
}시간 vs 공간 트레이드오프
때로는 시간복잡도와 공간복잡도 사이에서 선택해야 하는 상황이 발생합니다.
// 피보나치 수열 - 시간 우선 (메모이제이션)
function fibonacciMemo(n, memo = {}) {
if (n in memo) return memo[n];
if (n <= 2) return 1;
memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
return memo[n];
}
// 시간: O(n), 공간: O(n)
// 피보나치 수열 - 공간 우선 (반복문)
function fibonacciIterative(n) {
if (n <= 2) return 1;
let prev = 1, curr = 1;
for (let i = 3; i <= n; i++) {
const next = prev + curr;
prev = curr;
curr = next;
}
return curr;
}
// 시간: O(n), 공간: O(1)빅오 표기법 완전 정복
빅오 표기법의 기본 원칙
빅오 표기법은 최악의 경우를 기준으로 알고리즘의 성장률을 표현합니다.
핵심 원칙:
- 최고차항만 고려: O(n² + n + 1) → O(n²)
- 계수 무시: O(5n) → O(n)
- 상수항 무시: O(n + 100) → O(n)
// 잘못된 분석 예시와 올바른 분석
function complexFunction(n) {
// 1. 상수 연산들
const start = Date.now();
let result = 0;
// 2. O(n) 루프
for (let i = 0; i < n; i++) {
result += i;
}
// 3. O(n²) 중첩 루프
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
result += i * j;
}
}
// 4. 또 다른 O(n) 루프
for (let i = 0; i < n * 3; i++) {
result += 1;
}
return result;
}
// 잘못된 분석: O(1) + O(n) + O(n²) + O(3n) = O(1 + n + n² + 3n)
// 올바른 분석: O(n²) (최고차항만 고려)주요 복잡도 클래스
1. O(1) - 상수 시간
// 배열 인덱스 접근
function getElement(arr, index) {
return arr[index]; // 배열 크기와 무관하게 즉시 접근
}
// 해시맵 조회
const userMap = new Map();
function getUser(id) {
return userMap.get(id); // 평균적으로 O(1)
}2. O(log n) - 로그 시간
// 이진 탐색
function binarySearch(arr, target) {
let left = 0, right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
// 매번 탐색 범위가 절반으로 줄어듦3. O(n) - 선형 시간
// 배열 순회
function findElement(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1;
}
// 배열 필터링
function filterEvenNumbers(arr) {
return arr.filter(num => num % 2 === 0);
}4. O(n log n) - 선형 로그 시간
// 효율적인 정렬 알고리즘
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
const result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result.push(left[i++]);
} else {
result.push(right[j++]);
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}5. O(n²) - 이차 시간
// 중첩 루프
function findPairs(arr) {
const pairs = [];
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
pairs.push([arr[i], arr[j]]);
}
}
return pairs;
}
// 비효율적인 정렬
function selectionSort(arr) {
for (let i = 0; i < arr.length; i++) {
let minIndex = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
return arr;
}복잡도 성장률 비교
// 입력 크기별 연산 횟수 비교 (가상의 예시)
const n = 1000;
console.log('O(1):', 1); // 1
console.log('O(log n):', Math.log2(n)); // ~10
console.log('O(n):', n); // 1,000
console.log('O(n log n):', n * Math.log2(n)); // ~10,000
console.log('O(n²):', n * n); // 1,000,000
console.log('O(2^n):', Math.pow(2, 20)); // 1,048,576 (n=20일 때)JavaScript에서의 복잡도 분석
내장 메서드의 복잡도
JavaScript 내장 메서드들의 시간복잡도를 이해하는 것은 실무에서 매우 중요합니다.
배열 메서드
const arr = [1, 2, 3, 4, 5];
// O(1) - 상수 시간
arr.push(6); // 끝에 추가
arr.pop(); // 끝에서 제거
arr[0]; // 인덱스 접근
arr.length; // 길이 조회
// O(n) - 선형 시간
arr.unshift(0); // 앞에 추가 (모든 요소 이동)
arr.shift(); // 앞에서 제거 (모든 요소 이동)
arr.indexOf(3); // 요소 찾기
arr.includes(3); // 요소 포함 확인
arr.slice(1, 3); // 부분 배열 복사
arr.concat([6, 7]); // 배열 합치기
// O(n) - 순회 기반
arr.forEach(x => console.log(x));
arr.map(x => x * 2);
arr.filter(x => x > 2);
arr.reduce((sum, x) => sum + x, 0);
// O(n log n) - 정렬
arr.sort((a, b) => a - b);객체와 Map 비교
// 객체 - 일반적으로 O(1)이지만 보장되지 않음
const obj = {};
obj.key = 'value'; // O(1) 평균
obj.key; // O(1) 평균
delete obj.key; // O(1) 평균
// Map - 모든 연산이 O(1) 보장
const map = new Map();
map.set('key', 'value'); // O(1) 보장
map.get('key'); // O(1) 보장
map.delete('key'); // O(1) 보장
map.has('key'); // O(1) 보장Set을 활용한 최적화
// 배열에서 중복 제거 - 비효율적 방법 O(n²)
function removeDuplicatesArray(arr) {
const result = [];
for (const item of arr) {
if (!result.includes(item)) { // O(n) 연산이 n번 반복
result.push(item);
}
}
return result;
}
// Set을 활용한 효율적 방법 O(n)
function removeDuplicatesSet(arr) {
return [...new Set(arr)]; // Set 생성 O(n), 배열 변환 O(n)
}
// 성능 비교
const largeArray = Array(10000).fill().map(() => Math.floor(Math.random() * 1000));
console.time('Array method');
removeDuplicatesArray(largeArray);
console.timeEnd('Array method'); // 훨씬 오래 걸림
console.time('Set method');
removeDuplicatesSet(largeArray);
console.timeEnd('Set method'); // 빠름TypeScript에서의 복잡도 고려
// 제네릭을 활용한 효율적인 알고리즘
class OptimizedSearch<T> {
private data: T[];
private indexMap: Map<T, number>;
constructor(data: T[]) {
this.data = data;
this.buildIndex(); // O(n) 전처리
}
private buildIndex(): void {
this.indexMap = new Map();
this.data.forEach((item, index) => {
this.indexMap.set(item, index);
});
}
// O(1) 탐색
find(item: T): number {
return this.indexMap.get(item) ?? -1;
}
// O(n) 순차 탐색 (비교용)
findLinear(item: T): number {
return this.data.indexOf(item);
}
}
// 사용 예시
const searcher = new OptimizedSearch(['apple', 'banana', 'cherry']);
console.log(searcher.find('banana')); // O(1)프론트엔드 실무 적용 사례
1. 실시간 검색 최적화
// 비효율적인 실시간 검색 O(n) × 매 입력마다
function inefficientSearch(query, data) {
return data.filter(item =>
item.toLowerCase().includes(query.toLowerCase())
);
}
// 효율적인 실시간 검색 - 디바운싱 + 인덱싱
class SearchOptimizer {
constructor(data) {
this.data = data;
this.searchIndex = this.buildSearchIndex(data); // O(n) 전처리
this.debounceTime = 300;
}
buildSearchIndex(data) {
const index = new Map();
data.forEach((item, idx) => {
const words = item.toLowerCase().split(' ');
words.forEach(word => {
for (let i = 1; i <= word.length; i++) {
const prefix = word.substring(0, i);
if (!index.has(prefix)) {
index.set(prefix, new Set());
}
index.get(prefix).add(idx);
}
});
});
return index;
}
search(query) {
if (!query) return [];
const queryLower = query.toLowerCase();
const matchingIndices = this.searchIndex.get(queryLower) || new Set();
return Array.from(matchingIndices).map(idx => this.data[idx]);
}
// 디바운싱을 적용한 검색
debouncedSearch = this.debounce((query, callback) => {
const results = this.search(query);
callback(results);
}, this.debounceTime);
debounce(func, wait) {
let timeout;
return function executedFunction(...args) {
const later = () => {
clearTimeout(timeout);
func(...args);
};
clearTimeout(timeout);
timeout = setTimeout(later, wait);
};
}
}2. 대용량 리스트 가상화 (Virtualization)
// React에서 가상 스크롤 구현
class VirtualList {
constructor(containerHeight, itemHeight, totalItems) {
this.containerHeight = containerHeight;
this.itemHeight = itemHeight;
this.totalItems = totalItems;
this.visibleCount = Math.ceil(containerHeight / itemHeight);
this.buffer = 5; // 버퍼 아이템 수
}
// O(1) - 현재 화면에 보여야 할 아이템 계산
getVisibleRange(scrollTop) {
const startIndex = Math.floor(scrollTop / this.itemHeight);
const endIndex = Math.min(
startIndex + this.visibleCount + this.buffer,
this.totalItems
);
return {
startIndex: Math.max(0, startIndex - this.buffer),
endIndex,
offsetY: startIndex * this.itemHeight
};
}
}
// React 컴포넌트에서 사용
function VirtualListComponent({ items }) {
const [scrollTop, setScrollTop] = useState(0);
const virtualList = new VirtualList(400, 50, items.length);
const { startIndex, endIndex, offsetY } = virtualList.getVisibleRange(scrollTop);
const visibleItems = items.slice(startIndex, endIndex);
return (
<div
style={{ height: 400, overflow: 'auto' }}
onScroll={(e) => setScrollTop(e.target.scrollTop)}
>
<div style={{ height: items.length * 50, position: 'relative' }}>
<div style={{ transform: `translateY(${offsetY}px)` }}>
{visibleItems.map((item, index) => (
<div key={startIndex + index} style={{ height: 50 }}>
{item}
</div>
))}
</div>
</div>
</div>
);
}3. 상태 관리 최적화
// Redux에서 정규화를 통한 O(1) 접근
// 비효율적인 구조 O(n)
const inefficientState = {
posts: [
{ id: 1, title: 'Post 1', authorId: 1 },
{ id: 2, title: 'Post 2', authorId: 2 },
// ... 수천 개의 포스트
],
users: [
{ id: 1, name: 'User 1' },
{ id: 2, name: 'User 2' },
// ... 수천 명의 사용자
]
};
// 포스트 찾기 O(n)
function findPost(state, postId) {
return state.posts.find(post => post.id === postId);
}
// 효율적인 정규화된 구조 O(1)
const normalizedState = {
posts: {
byId: {
1: { id: 1, title: 'Post 1', authorId: 1 },
2: { id: 2, title: 'Post 2', authorId: 2 },
},
allIds: [1, 2]
},
users: {
byId: {
1: { id: 1, name: 'User 1' },
2: { id: 2, name: 'User 2' },
},
allIds: [1, 2]
}
};
// 포스트 찾기 O(1)
function findPostOptimized(state, postId) {
return state.posts.byId[postId];
}4. 메모이제이션을 활용한 최적화
// React.memo와 useMemo를 활용한 복잡도 최적화
import React, { useMemo, useState } from 'react';
function ExpensiveList({ items, filterCriteria }) {
// O(n) 연산을 메모이제이션으로 최적화
const filteredItems = useMemo(() => {
console.log('Filtering items...'); // 의존성 변경 시에만 실행
return items.filter(item => item.category === filterCriteria);
}, [items, filterCriteria]);
// O(n log n) 정렬 연산 메모이제이션
const sortedItems = useMemo(() => {
console.log('Sorting items...');
return [...filteredItems].sort((a, b) => a.name.localeCompare(b.name));
}, [filteredItems]);
return (
<div>
{sortedItems.map(item => (
<ExpensiveItem key={item.id} item={item} />
))}
</div>
);
}
// React.memo로 불필요한 리렌더링 방지
const ExpensiveItem = React.memo(({ item }) => {
console.log(`Rendering item ${item.id}`);
return <div>{item.name}</div>;
});성능 측정과 최적화 전략
1. 성능 측정 도구
// Performance API를 활용한 정확한 측정
class PerformanceMeasurer {
static measure(name, fn, ...args) {
const startTime = performance.now();
const result = fn(...args);
const endTime = performance.now();
console.log(`${name}: ${endTime - startTime}ms`);
return result;
}
static async measureAsync(name, fn, ...args) {
const startTime = performance.now();
const result = await fn(...args);
const endTime = performance.now();
console.log(`${name}: ${endTime - startTime}ms`);
return result;
}
static profile(name, fn, iterations = 1000) {
const times = [];
for (let i = 0; i < iterations; i++) {
const start = performance.now();
fn();
const end = performance.now();
times.push(end - start);
}
const avg = times.reduce((sum, time) => sum + time, 0) / iterations;
const min = Math.min(...times);
const max = Math.max(...times);
console.log(`${name} - Avg: ${avg.toFixed(3)}ms, Min: ${min.toFixed(3)}ms, Max: ${max.toFixed(3)}ms`);
}
}
// 사용 예시
const largeArray = Array(100000).fill().map(() => Math.floor(Math.random() * 1000));
PerformanceMeasurer.measure('Linear Search', findElement, largeArray, 500);
PerformanceMeasurer.measure('Binary Search', binarySearch, largeArray.sort(), 500);2. 브라우저 개발자 도구 활용
// Performance API 마크 사용
function measureComplexOperation() {
performance.mark('operation-start');
// 복잡한 연산 수행
const result = heavyComputation();
performance.mark('operation-end');
performance.measure('Complex Operation', 'operation-start', 'operation-end');
// 측정 결과 확인
const measures = performance.getEntriesByType('measure');
console.log(measures[measures.length - 1]);
return result;
}
// 메모리 사용량 모니터링
function monitorMemoryUsage() {
if (performance.memory) {
console.log('Used Memory:', performance.memory.usedJSHeapSize / 1024 / 1024, 'MB');
console.log('Total Memory:', performance.memory.totalJSHeapSize / 1024 / 1024, 'MB');
console.log('Memory Limit:', performance.memory.jsHeapSizeLimit / 1024 / 1024, 'MB');
}
}3. 알고리즘 최적화 패턴
투 포인터 기법
// 정렬된 배열에서 두 수의 합이 target인 쌍 찾기
// 브루트 포스 O(n²)
function twoSumBruteForce(nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return null;
}
// 투 포인터 O(n)
function twoSumOptimized(nums, target) {
let left = 0, right = nums.length - 1;
while (left < right) {
const sum = nums[left] + nums[right];
if (sum === target) {
return [left, right];
} else if (sum < target) {
left++;
} else {
right--;
}
}
return null;
}슬라이딩 윈도우 기법
// 고정 크기 윈도우의 최대 합 찾기
// 브루트 포스 O(n×k)
function maxSumBruteForce(arr, k) {
let maxSum = -Infinity;
for (let i = 0; i <= arr.length - k; i++) {
let currentSum = 0;
for (let j = i; j < i + k; j++) {
currentSum += arr[j];
}
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
// 슬라이딩 윈도우 O(n)
function maxSumOptimized(arr, k) {
if (arr.length < k) return null;
// 첫 번째 윈도우의 합 계산
let windowSum = arr.slice(0, k).reduce((sum, num) => sum + num, 0);
let maxSum = windowSum;
// 윈도우를 한 칸씩 이동하며 합 업데이트
for (let i = k; i < arr.length; i++) {
windowSum = windowSum - arr[i - k] + arr[i];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}결론 및 실무 가이드
시간복잡도와 공간복잡도는 단순한 이론이 아니라 실무에서 직접 성능에 영향을 미치는 핵심 개념입니다. 특히 프론트엔드 개발에서는 사용자 경험과 직결되므로 더욱 중요합니다.
핵심 요약
1. 복잡도 분석의 핵심
- 시간복잡도: 연산 횟수 기준의 효율성 측정
- 공간복잡도: 메모리 사용량 기준의 효율성 측정
- 빅오 표기법: 최악의 경우 성장률 표현
- 트레이드오프: 시간과 공간 간의 균형점 찾기
2. 프론트엔드에서의 중요성
- 사용자 경험: 빠른 응답 시간과 부드러운 인터랙션
- 메모리 관리: 모바일 환경에서의 제한된 리소스
- 확장성: 데이터 증가에 따른 성능 유지
- SEO 영향: 페이지 로딩 속도와 검색 순위
3. 최적화 우선순위
- 알고리즘 선택: 적절한 복잡도의 알고리즘 사용
- 자료구조 활용: Map, Set 등을 통한 효율적 데이터 접근
- 메모이제이션: 중복 계산 방지
- 가상화: 대용량 데이터 렌더링 최적화
실무 적용 로드맵
1단계: 기본 이해 (주니어 개발자)
// 기본적인 복잡도 분석 능력
const isO1 = (arr) => arr[0]; // O(1)
const isOn = (arr) => arr.forEach(); // O(n)
const isOn2 = (arr) => arr.forEach(() => arr.forEach()); // O(n²)2단계: 실무 적용 (중급 개발자)
- 프로젝트에서 성능 병목 지점 식별
- 적절한 자료구조와 알고리즘 선택
- 코드 리뷰 시 복잡도 고려
3단계: 최적화 전문가 (시니어 개발자)
- 시스템 전체의 성능 아키텍처 설계
- 복잡한 최적화 기법 적용
- 팀원들에게 성능 최적화 지식 전파
실무에서 자주 마주치는 상황들
상황 1: "배열에서 특정 조건의 아이템들을 찾아야 해요"
// ❌ 매번 전체 탐색 O(n)
const badApproach = (items) => items.filter(item => item.active);
// ✅ 인덱스 구축 후 O(1) 접근
class ItemManager {
constructor(items) {
this.items = items;
this.activeItems = items.filter(item => item.active);
this.activeIndex = new Set(this.activeItems.map(item => item.id));
}
isActive(itemId) {
return this.activeIndex.has(itemId); // O(1)
}
}상황 2: "리스트가 너무 커서 렌더링이 느려요"
// ❌ 모든 아이템 렌더링
const SlowList = ({ items }) => (
<div>
{items.map(item => <Item key={item.id} item={item} />)}
</div>
);
// ✅ 가상 스크롤링 적용
const FastList = ({ items }) => {
// VirtualList 컴포넌트 사용
return <VirtualList items={items} itemHeight={50} />;
};상황 3: "검색 기능이 타이핑할 때마다 버벅여요"
// ❌ 매번 전체 데이터 필터링
const slowSearch = (query, data) => {
return data.filter(item => item.name.includes(query));
};
// ✅ 디바운싱 + 인덱싱
const useOptimizedSearch = (data) => {
const searchIndex = useMemo(() => buildSearchIndex(data), [data]);
return useCallback(
debounce((query) => searchWithIndex(query, searchIndex), 300),
[searchIndex]
);
};지속적인 성능 모니터링
// 성능 모니터링 데코레이터
function performanceMonitor(target, propertyName, descriptor) {
const method = descriptor.value;
descriptor.value = function(...args) {
const start = performance.now();
const result = method.apply(this, args);
const end = performance.now();
if (end - start > 16) { // 16ms 이상 걸리면 경고
console.warn(`${propertyName} took ${end - start}ms`);
}
return result;
};
return descriptor;
}
class DataProcessor {
@performanceMonitor
processLargeDataset(data) {
// 데이터 처리 로직
}
}마무리
복잡도 분석은 더 나은 코드를 작성하기 위한 도구입니다. 무조건 최고의 복잡도를 추구하기보다는, 가독성, 유지보수성, 성능의 균형을 맞추는 것이 중요합니다.
728x90