0
가 나는 다음과 같은 질문에서 2N/3을 얻는 방법을 알아 낸 :Max-Heapify에서 최악의 경우 - 왜 2n/3을 얻을 수 있습니까?
Worst case in Max-Heapify - How do you get 2n/3?
"CLRS, 세 번째 판에서, 155 페이지, 그것은 주어진 MAX-HEAPIFY에서 해당 :
'어린이 하위 트리의 크기는 최대 2n/3입니다. 최악의 경우는 트리의 하단이 정확히 절반 만 가득 찼을 때 발생합니다.' "
그러나 나무의 최저 레벨이 정확히 절반 인 경우 궁금합니다. 전체, 우리는 다음을 얻습니다 :
우리는 미리 상정 한 이후T (N) < = T (2N/3) + 세타 (1)
그러면 하위 트리의 다음 재귀 호출이 서브 트리의 하부 레벨 (전체 가득 위의 재발을 얻기 위해 다른 쪽이 비어있는 동안이 쪽은 최대한 꽉 차 있음). 따라서, 다음의 호에 반복 될 것이다 :
T (N) < = T (N/2) + 세타 (1)
마다 재귀 호출 이후 동일하다.
실제로 재발생은 변하고 어떻게 우리는 여전히 마스터 정리를 사용할 수 있습니까?
그렇다면 a = 1이고 f (n) = n^0이므로 b가 무엇이든간에 최악의 실행 시간은 항상 O (lgn)가 될 것입니다. 무슨 b?
감사