목차
복잡도가 왜 필요한가?
복잡도 분석은 다음과 같은 이유로 필수적이다:
1. 성능 예측과 최적화
- 확장성 문제 사전 발견: 작은 데이터에서는 괜찮지만 데이터가 커질수록 급격히 느려지는 알고리즘을 미리 발견할 수 있다
- 병목 구간 식별: 어떤 부분이 성능에 가장 큰 영향을 주는지 파악할 수 있다
- 리팩토링 우선순위 결정: 어떤 코드를 먼저 최적화해야 하는지 객관적으로 판단할 수 있다
2. 알고리즘 선택과 비교
- 적절한 알고리즘 선택: 상황에 맞는 최적의 알고리즘을 선택할 수 있다
- 객관적 성능 비교: 여러 해결 방법 중 어떤 것이 더 효율적인지 비교할 수 있다
- 자료구조 선택 기준: Array vs Map, Set vs Object 등의 선택에 명확한 기준을 제공한다
3. 시스템 설계와 자원 관리
- 메모리 사용량 예측: 서버나 클라이언트의 메모리 사용량을 예측할 수 있다
- 서버 비용 계산: 클라우드 환경에서 필요한 컴퓨팅 자원을 미리 계산할 수 있다
- 사용자 경험 향상: 로딩 시간, 반응 속도 등을 개선할 수 있다
4. 기술 면접과 팀 커뮤니케이션
- 기술적 소통: 개발자 간에 성능에 대한 명확하고 객관적인 소통이 가능하다
- 코드 리뷰 품질: 코드의 효율성을 정량적으로 평가할 수 있다
- 기술 부채 관리: 장기적으로 문제가 될 수 있는 코드를 식별할 수 있다
시간 복잡도
시간 복잡도 기본 개념
시간 복잡도는 알고리즘이 입력 크기에 따라 실행 시간이 어떻게 증가하는지를 나타내는 개념이다. 주로 Big O 표기법으로 표현하며, 최악의 경우를 기준으로 한다.
주요 시간 복잡도 유형
O(1) - 상수 시간
입력 크기와 관계없이 항상 동일한 시간이 걸린다.
function getFirstElement(arr) {
return arr[0]; // 배열 크기와 무관하게 항상 같은 시간
}
function hasProperty(obj, key) {
return obj.hasOwnProperty(key); // 해시테이블 접근은 O(1)
}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;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}O(n) - 선형 시간
입력 크기에 비례해서 시간이 증가한다.
function findMax(arr) {
let max = arr[0];
for (let i = 1; i < arr.length; i++) { // n번 반복
if (arr[i] > max) max = arr[i];
}
return max;
}
function filterArray(arr, condition) {
const result = [];
for (const item of arr) { // n번 반복
if (condition(item)) result.push(item);
}
return result;
}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);
}
// JavaScript의 내장 sort도 O(n log n)
arr.sort((a, b) => a - b);O(n²) - 제곱 시간
중첩 반복문을 사용하는 알고리즘이다.
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - 1; j++) { // n × n
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
function findDuplicates(arr) {
const duplicates = [];
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] === arr[j] && !duplicates.includes(arr[i])) {
duplicates.push(arr[i]);
}
}
}
return duplicates;
}O(2ⁿ) - 지수 시간
모든 가능한 조합을 확인하는 알고리즘이다.
function fibonacci(n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2); // 각 호출마다 2번 재귀
}
function subsets(arr) {
if (arr.length === 0) return [[]];
const first = arr[0];
const rest = arr.slice(1);
const subsetsWithoutFirst = subsets(rest);
const subsetsWithFirst = subsetsWithoutFirst.map(subset => [first, ...subset]);
return [...subsetsWithoutFirst, ...subsetsWithFirst];
}성능 비교
입력 크기별 연산 횟수 비교:
| 복잡도 | n=10 | n=100 | n=1,000 | n=10,000 |
|---|---|---|---|---|
| O(1) | 1 | 1 | 1 | 1 |
| O(log n) | 3 | 7 | 10 | 13 |
| O(n) | 10 | 100 | 1,000 | 10,000 |
| O(n log n) | 30 | 700 | 10,000 | 130,000 |
| O(n²) | 100 | 10,000 | 1,000,000 | 100,000,000 |
| O(2ⁿ) | 1,024 | 불가능 | 불가능 | 불가능 |
공간 복잡도
공간 복잡도 기본 개념
공간 복잡도는 알고리즘이 실행되는 동안 사용하는 메모리 공간의 양을 입력 크기에 따라 나타내는 개념이다. 시간 복잡도와 마찬가지로 Big O 표기법으로 표현한다.
공간의 종류
고정 공간 (Fixed Space)
입력 크기와 무관하게 항상 동일한 공간을 사용한다.
- 변수, 상수
- 프로그램 코드 자체
가변 공간 (Variable Space)
입력 크기에 따라 달라지는 공간이다.
- 동적 할당 메모리
- 재귀 호출 스택
- 임시 데이터 구조
주요 공간 복잡도 유형
O(1) - 상수 공간
입력 크기와 관계없이 일정한 메모리만 사용한다.
function findMax(arr) {
let max = arr[0]; // 추가 변수 1개만 사용
for (let i = 1; i < arr.length; i++) {
if (arr[i] > max) max = arr[i];
}
return max;
}
function swapElements(arr, i, j) {
const temp = arr[i]; // 임시 변수 하나만 사용
arr[i] = arr[j];
arr[j] = temp;
}O(log n) - 로그 공간
재귀 이진 탐색처럼 호출 스택이 log n만큼 쌓인다.
function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
if (left > right) return -1;
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
else if (arr[mid] < target)
return binarySearchRecursive(arr, target, mid + 1, right);
else
return binarySearchRecursive(arr, target, left, mid - 1);
}
// 재귀 깊이가 log n이므로 O(log n) 공간O(n) - 선형 공간
입력 크기에 비례하는 추가 공간을 사용한다.
function reverseArray(arr) {
const reversed = []; // 새 배열 생성 - O(n) 공간
for (let i = arr.length - 1; i >= 0; i--) {
reversed.push(arr[i]);
}
return reversed;
}
function factorial(n) {
if (n <= 1) return 1;
return n * factorial(n - 1); // 재귀 스택 n개 - O(n) 공간
}
function createFrequencyMap(arr) {
const map = new Map(); // 최대 n개의 고유 요소 저장
for (const item of arr) {
map.set(item, (map.get(item) || 0) + 1);
}
return map;
}O(n²) - 제곱 공간
2차원 배열을 생성하는 경우다.
function createMatrix(n) {
const matrix = []; // n × n 크기의 2차원 배열
for (let i = 0; i < n; i++) {
matrix[i] = new Array(n).fill(0);
}
return matrix;
}
function multiplicationTable(n) {
const table = [];
for (let i = 1; i <= n; i++) {
table[i] = [];
for (let j = 1; j <= n; j++) {
table[i][j] = i * j;
}
}
return table;
}시간 vs 공간 트레이드오프
종종 시간 복잡도를 줄이기 위해 공간을 더 사용하거나, 그 반대의 경우가 있다.
메모이제이션으로 시간 절약, 공간 사용 증가
// 공간을 사용해서 시간을 절약
const memo = new Map();
function fibonacciMemo(n) {
if (memo.has(n)) return memo.get(n);
if (n <= 1) return n;
const result = fibonacciMemo(n - 1) + fibonacciMemo(n - 2);
memo.set(n, result);
return result;
}
// 시간: O(2^n) → O(n), 공간: O(1) → O(n)공간 절약, 시간 유지
// 공간을 절약해서 시간은 유지
function fibonacciIterative(n) {
if (n <= 1) return n;
let prev = 0, curr = 1; // O(1) 공간만 사용
for (let i = 2; i <= n; i++) {
const temp = prev + curr;
prev = curr;
curr = temp;
}
return curr;
}
// 시간: O(n), 공간: O(1)실제 예시: 배열 중복 제거
// 시간 우선 (Set 사용) - O(n) 시간, O(n) 공간
function removeDuplicatesWithSet(arr) {
return [...new Set(arr)];
}
// 공간 우선 (in-place) - O(n²) 시간, O(1) 공간
function removeDuplicatesInPlace(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] === arr[j]) {
arr.splice(j, 1);
j--;
}
}
}
return arr;
}프론트엔드에서의 활용
React 성능 최적화
// 메모리 사용량이 많은 경우
function ExpensiveComponent({ data }) {
const processedData = useMemo(() =>
data.map(item => ({
...item,
processed: heavyComputation(item)
})), [data]
); // 전체 데이터를 메모리에 복사
return <div>{/* 렌더링 */}</div>;
}
// 메모리 효율적인 경우
function EfficientComponent({ data }) {
return (
<div>
{data.map(item => (
<MemoizedItem key={item.id} data={item} />
))}
</div>
); // 필요할 때만 처리
}가상화 리스트
// 큰 리스트를 모두 렌더링 - O(n) 공간
function RegularList({ items }) {
return (
<ul>
{items.map(item => (
<li key={item.id}>{item.name}</li>
))}
</ul>
);
}
// 보이는 부분만 렌더링 - O(1) 공간
function VirtualizedList({ items, itemHeight, containerHeight }) {
const [scrollTop, setScrollTop] = useState(0);
const startIndex = Math.floor(scrollTop / itemHeight);
const endIndex = Math.min(
startIndex + Math.ceil(containerHeight / itemHeight) + 1,
items.length
);
const visibleItems = items.slice(startIndex, endIndex);
return (
<div style={{ height: containerHeight, overflow: 'auto' }}>
<div style={{ height: items.length * itemHeight }}>
<div style={{ transform: `translateY(${startIndex * itemHeight}px)` }}>
{visibleItems.map(item => (
<div key={item.id} style={{ height: itemHeight }}>
{item.name}
</div>
))}
</div>
</div>
</div>
);
}검색 기능 최적화
// 비효율적인 검색 - O(n²)
function searchProducts(products, query) {
return products.filter(product =>
Object.values(product).some(value =>
value.toString().toLowerCase().includes(query.toLowerCase())
)
);
}
// 효율적인 검색 - O(n) + 인덱싱
class ProductSearch {
constructor(products) {
this.products = products;
this.searchIndex = this.buildSearchIndex(products);
}
buildSearchIndex(products) {
const index = new Map();
products.forEach((product, idx) => {
const searchText = Object.values(product).join(' ').toLowerCase();
const words = searchText.split(/\s+/);
words.forEach(word => {
if (!index.has(word)) index.set(word, new Set());
index.get(word).add(idx);
});
});
return index;
}
search(query) {
const queryWords = query.toLowerCase().split(/\s+/);
let resultIndices = null;
queryWords.forEach(word => {
const wordIndices = this.searchIndex.get(word) || new Set();
if (resultIndices === null) {
resultIndices = new Set(wordIndices);
} else {
resultIndices = new Set([...resultIndices].filter(x => wordIndices.has(x)));
}
});
return resultIndices ?
[...resultIndices].map(idx => this.products[idx]) : [];
}
}실무 적용 가이드
1. 성능 측정 도구 활용
// 실행 시간 측정
function measureTime(fn, ...args) {
const start = performance.now();
const result = fn(...args);
const end = performance.now();
console.log(`실행 시간: ${end - start}ms`);
return result;
}
// 메모리 사용량 측정 (Node.js)
function measureMemory(fn, ...args) {
const memBefore = process.memoryUsage().heapUsed;
const result = fn(...args);
const memAfter = process.memoryUsage().heapUsed;
console.log(`메모리 사용량: ${(memAfter - memBefore) / 1024 / 1024}MB`);
return result;
}2. 적절한 자료구조 선택
// 검색이 주된 용도 - Map/Set 사용 (O(1))
const userMap = new Map();
userMap.set('user1', { name: 'John', age: 30 });
// 순서가 중요한 경우 - Array 사용
const todoList = [
{ id: 1, text: '첫 번째 할 일', completed: false },
{ id: 2, text: '두 번째 할 일', completed: true }
];
// 고유값만 필요한 경우 - Set 사용
const uniqueTags = new Set(['react', 'javascript', 'web', 'react']);3. 메모리 누수 방지
// 이벤트 리스너 정리
useEffect(() => {
const handleResize = () => {
// 리사이즈 처리
};
window.addEventListener('resize', handleResize);
return () => {
window.removeEventListener('resize', handleResize);
};
}, []);
// WeakMap, WeakSet 활용
const elementData = new WeakMap();
function attachData(element, data) {
elementData.set(element, data);
}
// element가 GC되면 관련 데이터도 자동으로 정리됨4. 점진적 최적화
// 1단계: 기본 구현
function processData(data) {
return data.map(item => transform(item)).filter(item => isValid(item));
}
// 2단계: 불필요한 중간 배열 제거
function processDataOptimized(data) {
const result = [];
for (const item of data) {
const transformed = transform(item);
if (isValid(transformed)) {
result.push(transformed);
}
}
return result;
}
// 3단계: 제너레이터 사용으로 지연 평가
function* processDataLazy(data) {
for (const item of data) {
const transformed = transform(item);
if (isValid(transformed)) {
yield transformed;
}
}
}5. 성능 모니터링
// Web Vitals 측정
import { getCLS, getFID, getFCP, getLCP, getTTFB } from 'web-vitals';
getCLS(console.log);
getFID(console.log);
getFCP(console.log);
getLCP(console.log);
getTTFB(console.log);
// React 컴포넌트 성능 프로파일링
function ProfiledComponent({ data }) {
const renderStart = performance.now();
useEffect(() => {
const renderEnd = performance.now();
console.log(`컴포넌트 렌더링 시간: ${renderEnd - renderStart}ms`);
});
return <div>{/* 컴포넌트 내용 */}</div>;
}복잡도 분석을 통해 더 효율적이고 확장 가능한 애플리케이션을 개발할 수 있다. 항상 완벽한 최적화를 추구하기보다는, 실제 사용자 경험에 영향을 주는 부분을 우선적으로 최적화하는 것이 중요하다.
