런타임 점화식의

Question

단지 퀴즈에 있었다 : T (N) = 4T (N SQRT()) + 5

제가 교체를 사용하여 단순화 F (k)를 얻었다 = 4F (K/2) + 5

마스터 정리를 사용하면 O (logn)라고 추측했습니다. 정확합니까?

Answer 1

그런 다음

F(n) = T(2^n) 

정의 우리는 마스터 정리하여

F(n) = 4F(n/2) + 5 

, 우리는

a = 4 
b = 2 
f(n) = 5 = O(1) = O(m^0), so c = 0 
0 < 2 = log_2(4) 

그래서 우리는 마스터 정리의 경우 1 걸 가지고있다. 경우 1, 우리는 그래서

T(2^n) = Theta(n^2) 

따라서

T(n) = Theta(log(n^2)) = Theta(2logn) = Theta(log n) 

는 그래서 그래, 당신의 대답은 올바른 것 같다

F(n) = Theta(n^2) 

있습니다.