마스터 정리1

• 

  [알고리즘] 마스터 정리(도사 정리) 도사정리 재귀 관계씩으로 표현한 알고리즘의 동작 시간을 점근적으로 계산하여 간단하게 계산하는 방법으로, 재귀 알고리즘의 시간 복잡도를 결정해주는 블랙박스 툴이다. 재귀 알고리즘의 점화식(recurrence)으로부터 시간 복잡도를 결정하며, 표준 점화식으로만 가능하다. f(n)이 점근적으로 양이라는 말은 충분히 큰 n에 대해 f(n)이 양이라는 의미이다. 표준 점화식 3개의 파라미터로 구성된 대부분 재귀 알고리즘을 분석할 때 사용할 수 있는 점화식을 표준 점화식이라 한다. 여기서 a는 재귀호출의 수, b는 입력 크기가 줄어드는 정도, d는 일반 과정에서 소요되는 시간 복잡도의 지수이다. (a는 작을수록 좋으며, b는 클수록 좋다.) a, b, d는 모두 n과 독립적인 상수이고, d=0이라면 상수 시간을 뜻.. Algorithm 2022. 4. 9.