마스터 정리 계산기
분할정복 점화식 T(n)=aT(n/b)+f(n) 에 a·b·f(n)의 지수를 넣으면 마스터 정리의 세 경우 중 어디에 해당하는지 판정해 Θ 점근 복잡도를 구합니다.
f(n) = n^d · (log n)^k
점근 복잡도
Θ(n · log n)
임계 지수 c = log_b(a) = 1
사용 방법
- 1T(n)=aT(n/b)+f(n) 의 a(재귀 호출 수), b(크기를 줄이는 배수)를 입력합니다.
- 2f(n)=n^d·(log n)^k 꼴로 d(다항 지수)와 k(로그 거듭제곱)를 입력합니다.
- 3임계 지수 c=log_b(a) 와 세 경우 중 어디에 해당하는지 확인합니다.
- 4Θ(...) 로 표기된 점근 복잡도를 확인합니다.
자주 묻는 질문
병합정렬·카라추바처럼 문제를 b등분해 a번 재귀 호출하고 f(n)만큼 추가 작업을 하는 점화식 T(n)=aT(n/b)+f(n)의 점근 복잡도를, 재귀 트리를 직접 펼치지 않고도 세 경우로 나눠 즉시 읽어내는 정리입니다.
재귀 트리를 맨 밑(잎)까지 펼쳤을 때 잎에서 하는 일의 총합이 정확히 n^c입니다. f(n)(각 층에서 추가로 하는 일)이 이 n^c보다 빨리 크는지 늦게 크는지가 전체 복잡도를 결정합니다.
f(n)의 지수 d가 c보다 작으면(경우1) 잎에서 하는 일이 지배해 Θ(n^c), d와 c가 같으면(경우2) 모든 층이 비슷해 Θ(n^c·log^{k+1}n), d가 c보다 크면(경우3) 맨 위층(f(n) 자체)이 지배해 Θ(n^d·log^k n)이 됩니다.
아니요. 이 계산기는 f(n)=n^d·(log n)^k 꼴(다항식×로그)만 다룹니다. f(n)=n/log n이나 f(n)=2^n처럼 이 형태를 벗어나면 마스터 정리 자체가 적용되지 않아(정리의 조건을 안 만족) 아커만 함수 확장판이나 재귀 트리를 직접 펼치는 다른 방법이 필요합니다.
이 계산기가 다루는 다항식×로그 꼴에서는 d가 c보다 크면 정칙조건(a·f(n/b)≤κ·f(n))이 자동으로 성립한다는 사실이 알려져 있어 따로 검사하지 않습니다. 더 복잡한 f(n)을 쓰는 경우라면 정칙조건을 직접 확인해야 합니다.
알아두면 좋은 점
- 카라추바(a=3,b=2,f(n)=n)는 경우1로 Θ(n^log₂3)≈Θ(n^1.585), 병합정렬(a=2,b=2,f(n)=n)은 경우2로 Θ(n log n)이 나옵니다. 이런 이름 붙은 알고리즘들과 대조해 검증했습니다.
- f(n)이 n^d·(log n)^k 꼴을 벗어나면(다항식×로그가 아니면) 이 계산기로는 판정할 수 없습니다.
- a<1 이거나 b≤1이면 애초에 의미 있는 분할정복 점화식이 아니라 계산하지 않습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 3일 · 결과는 참고용 추정치입니다.