순환식 \mathrm{T}(n)=\mathrm{T}(n/3)+\math… | [7급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지

1[7급 서울시 알고리즘] 26년 1회차
순환식 T(n)=T(n/3)+T(2n/3)+n (n>1), T(1)=1\mathrm{T}(n)=\mathrm{T}(n/3)+\mathrm{T}(2n/3)+n\ (n>1),\ \mathrm{T}(1)=1로 표현되는 알고리즘의 점근적 시간 복잡도로 가장 옳은 것은?
1
Θ(n)\Theta(n)
2
Θ(nlog⁡n)\Theta(n\log n)
3
Θ(n1.5)\Theta(n^{1.5})
4
Θ(n2)\Theta(n^{2})
해설

점근적 시간 복잡도는 Θ(nlog⁡n)\Theta(n\log n)이다.

재귀 트리로 펼치면 각 레벨의 비용 합이 n/3+2n/3=nn/3+2n/3=n으로 최대 nn이다.

가장 짧은 가지의 깊이는 log⁡3n\log_3 n, 가장 긴 가지의 깊이는 log⁡3/2n\log_{3/2} n으로 모두 Θ(log⁡n)\Theta(\log n)이므로, 전체 비용은 레벨당 nn × 깊이 log⁡n\log n이 된다.

  • Θ(n)\Theta(n): 비용 nn인 레벨이 로그 개만큼 쌓이므로 선형보다 크다.
  • Θ(n1.5)\Theta(n^{1.5}): 레벨당 비용이 nn을 넘지 않고 깊이도 로그이므로 지나치게 크다.
  • Θ(n2)\Theta(n^{2}): 레벨당 비용 nn이 로그 깊이만큼만 쌓이므로 제곱에 이르지 않는다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 서울시 알고리즘] 26년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 서울시 알고리즘 기출문제 암기장 전체 보기