병합 정렬 재귀 트리의 높이

Question

나는 트리의 높이가 n의 로그 b이고 n이 2이고 입력의 크기가 10 인 요소를 파악하는 방법을 배우고 있습니다. 병합 정렬 작업.

분할이 완료되는 횟수는 내가 이해로까지 나무의 높이, 그리고 트리의 레벨 수는 높이 + 1

입니다하지만 당신은 (병합 정렬에 대해) 가지고가는 경우 10의 log2는 1을 얻습니다. 트리를 그릴 경우 적어도 2 회 재귀가 발생합니다.

어디로 잘못 갔습니까? (나는 여기에서 의미를 갖기를 바랍니다)

참고 : 나는 자습을하고 있습니다. 숙제가 아닙니다!

Answer 1

로그 ₂ (10) = 3.321928094887362 ... 어떤 경우

는 재귀 콜 깊이는 기본적으로 "로그 (N)의 순서는"의미 O(log(n))이다. O (log (n)) 알고리즘의 실제 호출 깊이는 k*log(n)+c이거나 심지어 k*log(n)+ α (n)/log(log(n))+c 일 수 있습니다.