결정 트리의 리프 최단 깊이 (비교 정렬 알고리즘)

Question

결정 트리의 길이가 이며 가능한 가장 짧은 깊이는 comparison sorting algorithm입니다.

어 로그에 따라 바뀌나요?

Answer 1

모든 요소를 ​​확인하고 데이터가 이미 정렬 된 것을 확인하면 절대적인 최상의 경우가 발생합니다.

이렇게하면 n-1의 비교 결과가되고 리프의 깊이는 n-1이됩니다.

실질적으로이 문제는 insertion sort에 발생합니다.

알고리즘에 따라 달라 집니까?

물론입니다. 알고리즘의 가장 좋은 경우는 좋은 지표입니다. O (n log n)의 가장 좋은 경우가 가장 짧은 깊이는 O (n)이 가장 좋은 경우의 최단 깊이보다 길 것입니다.