임의의 삽입을 수행하는 초기 BST가 비어 있다고 가정하면이 BST의 평균 높이를 어떻게 알 수 있습니까? 이것에 대한 점화식에서반복 BST의 평균 높이를 찾는 관계/시간 복잡도
H(T) = 1 + max(H(T.left), H(T.right))
내 생각 엔이 T(n) = 1 + 2*T(n/2) 것입니다,하지만 난이 맞는지 확실하지 않다 : (I 틀리지 않는 경우)이 대한 표현/의사가 될 것입니다.
내 반복 관계가 맞다면 여기 내 딜레마가 있습니다. 평균 높이 알고리즘의 평균 복잡도는 어떻게 계산합니까?
일반적으로 평균 사례 분석은 더 복잡하며 정상적인 최악의 경우에 사용하는 것과 동일한 big-O 기술을 실제로 사용할 수 없습니다. 당신의 신장 정의가 정확하지만, 재발에 대한 번역은 아마도 그때보다 복잡 할 것입니다. 우선, T(n) = 1 + T(n/2)을 의미했을 것입니다 (이것은 버전이 O (n)을 제공하는 동안 O (log n) 높이를 가짐) 값이 오른쪽과 왼쪽으로 균등하게 50-50으로 나뉘어지지 않습니다.
search a bit 당신은 BST의 평균 높이에 많은 물질이 있다는 것을 알게 될 것입니다. 예를 들어, one of the results I got은 n이 커질수록 BST의 예상 높이는 4.3 * (log n)이되는 경향이 있지만 복잡한 수학을 많이 거쳐 간다고합니다.
T (n/2) + c 여기서 우리는 두 부분으로 우리의 배열을 나눕니다. 그러나 우리는 단 하나의 부분 만 사용하여 search.if를 만듭니다. (mid + 1 ..... j) 에서 검색하고 그 중간 값이 작 으면 (i ... mid) 검색하므로 단일 하위 배열로만 작업합니다
이것은 간단한 반복 관계가 아닙니다. n이 있습니다! 입력 시퀀스 S_i. 각 시퀀스는 BST T (S_i)를 생성하지만 여러 시퀀스가 동일한 트리를 생성 할 수 있습니다. 각 나무의 높이는 H (T (S_i))입니다. (sum_ {i = 0..n!} H (T (S_i)))/n!을 알아 내야합니다. 자, H (T (s))를 계산하는 방법은? – Gene