프로그래머가 알아야 할 8 가지 시간 복잡도
Source
Evernote/Papers/8 time complexities that every programmer should know.md
Summary
이 문서는 알고리즘의 성능을 평가하고 확장성을 예측하기 위해 필수적인 8 가지 주요 시간 복잡도(Big-O 표기법)를 소개한다. 입력 크기(n)에 따른 연산 횟수의 증가율을 기준으로 O(1) 상수 시간부터 O(n!) 팩토리얼 시간까지의 복잡도를 분류하며, 각 복잡도별 대표적인 알고리즘 예시(예: 이진 탐색, 병합 정렬, 버블 정렬 등)와 코드 구현 예시를 제공한다. 개발자가 서로 다른 해결책을 비교하고 더 효율적인 구현을 선택하는 데 도움을 주는 실용적인 가이드이다.
Key Points
- 시간 복잡도는 알고리즘이 실행되는 기계와 무관하게 입력 크기(n)에 따른 연산 횟수의 증가율을 Big-O 표기법으로 나타낸 것이다.
- 주요 8 가지 시간 복잡도: O(1) 상수, O(log n) 로그, O(n) 선형, O(n log n) 선형 로그, O(n^2) 2 차, O(n^3) 3 차, O(2^n) 지수, O(n!) 팩토리얼.
- 각 복잡도별 대표 예시: O(1)은 홀짝 판별, O(log n)은 정렬 배열의 이진 탐색, O(n)은 정렬되지 않은 배열의 최대값 찾기, O(n log n)은 병합 정렬, O(n^2)은 버블 정렬, O(2^n)은 부분집합 찾기, O(n!)은 순열 찾기 등.
- 알고리즘의 시간 복잡도를 이해하면 코드의 확장성(scalability)을 평가하고 동일한 문제에 대한 다양한 해결책 중 성능이 더 우수한 것을 선택할 수 있다.