재발 해결

Question

재귀 트리를 사용하여 주어진 재귀를 해결하려고합니다. T(n) = 3T(n/3) + n/lg n.

첫 번째 레벨에서 (n/3)/(log(n/3)) + (n/3)/(log(n/3)) + (n/3)/(log(n/3)) = n/(log(n/3)).

두 번째 레벨에서는 그 것으로 밝혀졌습니다 n/(log(n/9)).

위의 방정식을 형태로 일반화 할 수 있습니까? n.loglogn

이것은 내가 일반적인 의심입니다. 이것에 대한 통찰력이 필요합니다.

참고 : 모든 기능이 있어야합니다 Theta(n^k log^k (n)) 그 함수에서 k는> = 1해야합니다. 그리고이 경우 k는 -1이므로 마스터 정리가 그림에 나오지 않습니다.

Answer 1

마스터 정리가 적용되지 않습니다.

t (n) = 3t (n/3) + n/logn.

g (n) = t (n)/n로하자.

그런 다음 ng (n) = 3(N/3)*G (N/3) + N/Logn.

따라서

g (n) = g (n/3) + 1/log n.

이것은 g (n) = 합 1/log n + 1/log n/3 + 1/log n/9 +를 제공합니다.

= theta (합 1/logn + 1/(logn -1) + 1/(log n -2) + ...) = theta (1/x 사이의 적분 1/x) = theta (log log n).

따라서 t (n) = ng (n) = theta (n로그 로그.)

당신은 그것을 바로 추측했습니다.

Answer 2

트리를 사용하여 질문을 시각화하는 경우 각 순위의 합이 다음과 같습니다.

• 순위 0 :

(n/log (n)와 같음) - 순위 1 :

그리고 일반적인 합계와 함께 n/log(n/(3^i)) 각 순위에 대해, 나는 현재 순위입니다. 그래서 모두 함께 얻습니다.

방정식을 열면 다음과 같습니다.

(끝에서 시작하여 뒤로 가기 .. 먼저 i = log (base3) n을 다음 뒤로 돌아가는 경우)

로그베이스는 theta에서 중요하지 않기 때문에 우리는 다음을 얻습니다.

그것은 :

(시그마에서) :

이는 다음과 같은 고조파 시리즈입니다.

그리고 LN은 E의 기초가있는 로그이고 Theta에서는 로그베이스가 중요하지 않기 때문에 마침내 다음과 같습니다.

다음과 같습니다.

그래서 그것은 theta (n log log n)입니다.