t (n) = 2t (n/2) + n^0.5/logn은 마스터 정리를 사용하여 해결할 수 있습니까?

Question

나는 내 친구와 논쟁이있다. 어제 시험을 치렀다. 나는 그럴 수 없다고 말했고, 그는 1이 될 것이라고 말했다. 아마 맞을지 모르겠다.하지만 나는 이유를 이해하는 것처럼 보인다. 미리 감사드립니다.

Answer 1

n이 1보다 큰 경우 n (0.5/log n)은 exp (0.5)의 상수 값을가집니다. 이것은 매우 쉽게 증명 될 수 있습니다 :

x = n^(0.5/log n) 
    log(x) = (log n) * 0.5/(log n) = 0.5 
=> x = exp(0.5) = 1.64872... 

결과적으로 표현식의 두 번째 용어는 상수로 처리 될 수 있습니다. 일정한 제 2 기의 경우 수식은 t(n) = 2t(n/2) + 1과 같으며 복잡도 O (n)입니다.

예, 친구가 옳습니다. 이것은 case 1에 해당하며, 여기서 f (n) ∈ O (n^c)의 c 값은 0입니다.