순환식 \mathrm{T}(n)=\mathrm{T}(n/3)+\math… | [7급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지
1[7급 서울시 알고리즘] 26년 1회차
순환식 로 표현되는 알고리즘의 점근적 시간 복잡도로 가장 옳은 것은?1
2
3
4
해설
점근적 시간 복잡도는 이다.
재귀 트리로 펼치면 각 레벨의 비용 합이 으로 최대 이다.
가장 짧은 가지의 깊이는 , 가장 긴 가지의 깊이는 으로 모두 이므로, 전체 비용은 레벨당 × 깊이 이 된다.
- : 비용 인 레벨이 로그 개만큼 쌓이므로 선형보다 크다.
- : 레벨당 비용이 을 넘지 않고 깊이도 로그이므로 지나치게 크다.
- : 레벨당 비용 이 로그 깊이만큼만 쌓이므로 제곱에 이르지 않는다.
오류나 개정된 내용이 보이면 알려주세요