introsort가 재귀 깊이 한도에서 heapsort로 전환합니다. 최악 시간과 stack 상한은 어떻게 연결되나요?

꼬리 질문을 독립 문항으로 확장했습니다. 원래 문항에서 맥락 보기 →

잠깐, 답변을 보기 전에
먼저 내 말로 설명해 볼까요?

답변과 점검 포인트 펼치기답변 접기

구두 답변

정의를 외우기보다, 원리와 조건을 연결해 설명해 보세요.

분할이 계속 불균형하면 깊이가 커지는 것을 신호로 heapsort로 전환해 최악 O(n log n)을 확보하는 접근입니다. 작은 구간 처리와 stack 관리의 계약도 따로 봅니다.

깊이 제한만 넣고 나머지를 버리면 정렬이 아닙니다. 작은 구간 재귀·큰 구간 반복은 stack을 줄일 수 있지만 시간 최악을 단독 해결하지 않습니다. 정렬·역순·동일값에서 비교·깊이·결과를 검사합니다.

이해가 드러나는 지점을 확인해 보세요.

분할이 계속 불균형하면 깊이가 커지는 것을 신호로 heapsort로 전환해 최악 O(n log n)을 확보하는 접근입니다. 작은 구간 처리와 stack 관리의 계약도 따로 봅니다.
정렬·역순·동일값에서 비교·깊이·결과를 검사합니다.

놓치기 쉬운 조건과 오해를 짚어 보세요.

다음 핵심 구분을 반대로 설명하거나 성립 조건을 생략한다: 분할이 계속 불균형하면 깊이가 커지는 것을 신호로 heapsort로 전환해 최악 O(n log n)을 확보하는 접근입니다.

하나 더 질문하며 이해의 범위를 넓혀 보세요.

득점·감점 포인트는 학습용 자기 점검 기준이며, 특정 회사의 실제 채점표가 아닙니다.