반복 관계 : T (n/16) + n log n

Question

마스터 정리를 적용 할 수 있습니까?

T (n) = 2T (n/16) + n log n에 대해 마스터 정리는 어떻게 적용하나요?

나는 a = 2, b = 16이되고 나는 c과 k에 대해 확실하지 않습니다.

Answer 1

log (n) 용어가 없더라도 각 수준에서 하위 문제 당 작업 감소가 우세합니다 (b> a). 따라서 제 생각에는 복잡성은 최고 수준, 즉 O (nlogn)에서 수행 된 작업에 의해 결정됩니다.

Answer 2

이와 같은 반복 관계 T(n) = a⋅T(n/b) + f(n)을 해결하려면 e = logb(a)을 계산해야합니다. (AN ε > 0에 대한) 그런 다음

:

1. f(n) ∈ O(ne - ε) ⇒ T(n) ∈ Θ(ne)
2. f(n) ∈ Θ(ne) ⇒ T(n) ∈ Θ(ne⋅log(n))
3. f(n) ∈ Ω(ne + ε) ⇒ 세부 사항 Masters Theorem를 참조 자세한 내용은 T(n) ∈ Θ(f(n))

. 따라서 귀하의 경우

: a = 2, b = 16 ⇒ e = log16(2) = 0.25는 경우 3,
그렇게 T(n)이 Θ(n log n)에 대한 보유하고 있습니다.