목록Master theorem (1)

YYYEJI

[Algorithm] 마스터 정리 (Master Theorem)

마스터 정리 (Master Theorem)란? T(n)=aT(n/b)+f(n) 형식의 재귀적인 알고리즘을 계산하기 위한 방법입니다. ① If f(n) = O(nˡºᵍ𝚋ª⁻ᵋ) Ɛ>0, then T(n) = θ(nˡºᵍ𝚋ª). ② If f(n) = θ(nˡºᵍ𝚋ª), then T(n) = θ(nˡºᵍ𝚋ªlg n). ③ If f(n) = Ω(nˡºᵍ𝚋ª⁺ᵋ) Ɛ>0 and a f(n/b) ≤ c f(n), T(n) = θ(f(n)) 문제를 풀면서 이해를 해보도록 하겠습니다. Excercise 1: T(n) = 4T(n/2) + n T(n)=aT(n/b)+f(n)을 보면 a = 4, b = 2, f(n) = n임을 알 수 있습니다. Case 1에 만족함을 확인했습니다. Excercise 2: T(n) = 4T..
Algorithm 2023. 4. 16. 19:27
이전 Prev 1 Next 다음