정의
O(n log n)은 분할(log n)과 처리(n)를 곱한 시간 복잡도입니다. 비교 기반 정렬 알고리즘의 이론적 하한선입니다.
핵심 특성
- ✓분할 정복 알고리즘의 복잡도
- ✓효율적인 정렬의 한계
- ✓O(n)보다 느리고 O(n²)보다 빠름
활용 사례
이런 상황에서 사용됩니다:
🔀
병합 정렬
나누고 합치면서 정렬
⚡
퀵 정렬
피벗 기준 분할
🏔️
힙 정렬
힙으로 최댓값 추출
복잡도
시간 복잡도
최선
O(n log n)
평균
O(n log n)
최악
O(n log n)
공간 복잡도
O(n)
시각화로 더 깊이 이해하기
단계별 애니메이션과 코드 실행을 통해 알고리즘이 어떻게 동작하는지 직접 확인하세요.
시각화 시작하기