시간 복잡도 및 공간 복잡도 이해

카테고리

프로그래밍/소프트웨어 개발

서브카테고리

개발 툴

대상자

- 소프트웨어 개발자 (중간 수준): 알고리즘 성능 분석 및 최적화를 위한 기초 지식 습득

- 기초 이해 필요: Big O 표기법, 시간/공간 복잡도 개념

핵심 요약

• 시간 복잡도: 알고리즘의 실행 시간이 입력 크기와의 관계를 나타냄 (예: O(1), O(n), O(n²)).
• 공간 복잡도: 알고리즘 실행 시 추가 메모리 사용량을 나타냄 (예: O(1)은 고정 메모리, O(n)은 입력에 비례).
• Big O 표기법: 알고리즘 성능을 일반화하여 표현 (예: O(log n)은 이진 탐색).

섹션별 세부 요약

1. 시간 복잡도의 핵심 개념

• O(1) (상수 시간): 입력 크기와 관계없이 실행 시간이 동일 (예: 배열의 첫 번째 요소 접근).
• O(n) (선형 시간): 입력 크기와 비례하여 실행 시간 증가 (예: 배열의 최대값 찾기).
• O(n²) (제곱 시간): 중첩 루프로 인해 입력 크기 증가 시 성능 급격히 저하 (예: 모든 중복 쌍 찾기).
• O(log n) (로그 시간): 문제를 반복적으로 절반으로 줄여 가며 처리 (예: 이진 탐색).

2. 공간 복잡도의 핵심 개념

• O(1) (상수 공간): 입력 크기와 무관한 고정 메모리 사용 (예: 배열 합 계산).
• O(n) (선형 공간): 입력 크기와 비례하여 추가 메모리 사용 (예: 배열의 두 배 값으로 새로운 배열 생성).

3. 실무 예시 및 측정

• JavaScript/C# 예시: 다양한 복잡도의 알고리즘을 테스트해 실행 시간 및 메모리 사용량 비교 (예: O(1)은 1000개/100만 개 배열 모두 동일한 시간).
• 시간 복잡도 비교: 동일한 입력 크기에서 O(1) < O(log n) < O(n) < O(n log n) < O(n²) 순으로 실행 시간 증가.

결론

• 핵심 팁: 알고리즘 선택 시 시간/공간 복잡도를 고려해 성능을 최적화 (예: O(n²) 알고리즘은 데이터 크기가 클 때 피해야 함).
• 예시: 이진 탐색(O(log n))은 대규모 데이터에서 효율적이며, 배열 접근(O(1))은 최적의 성능 제공.