1/8
Loading...
🌳O(n log n)이란?
트리 구조로 "왜 n × log n인지" 봅시다! 📊 핵심 포인트: • 레벨 수 = log₂(n) = 반으로 나누는 횟수 • 각 레벨에서 n개 요소 처리 이 트리를 보세요: 각 레벨 오른쪽에 "= 8개"가 있죠? 매 레벨마다 총 n개를 처리합니다!
Loading...
트리 구조로 "왜 n × log n인지" 봅시다! 📊 핵심 포인트: • 레벨 수 = log₂(n) = 반으로 나누는 횟수 • 각 레벨에서 n개 요소 처리 이 트리를 보세요: 각 레벨 오른쪽에 "= 8개"가 있죠? 매 레벨마다 총 n개를 처리합니다!
O(n log n)은 분할(log n)과 처리(n)를 곱한 시간 복잡도입니다. 비교 기반 정렬 알고리즘의 이론적 하한선입니다.