다음은 x^n을 구하는 알고리즘이다. 이 알고리즘의 시간 복잡도는? (… | [7급 국가직 자료구조론] 14년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 14년 1회차
다음은 xnx^n을 구하는 알고리즘이다. 이 알고리즘의 시간 복잡도는? (단, n > 0이며, even(m)은 m이 짝수일 때 참을 반환하고 그렇지 않을 때 거짓을 반환하는 함수이다)
int PowersRec(int x, int n)
{
int Pow;
if (n == 1)
Pow = x;
else {
if (even(n))
Pow = PowersRec(x*x, n/2);
else
Pow = x * PowersRec(x*x, (n-1)/2);
}
return (Pow);
}
1
Θ(1)\Theta(1)
2
Θ(log⁡n)\Theta(\log n)
3
Θ(n)\Theta(n)
4
Θ(nlog⁡n)\Theta(n \log n)
해설

이 알고리즘의 시간 복잡도는 Θ(log⁡n)\Theta(\log n)이다.

재귀 호출마다 지수 n이 n/2 또는 (n-1)/2로 절반씩 줄고, 각 호출은 비교·곱셈 같은 상수 시간 작업만 한다.

T(n)=T(n/2)+cT(n)=T(n/2)+c
T(n)=clog⁡2n+T(1)=Θ(log⁡n)T(n)=c\log_2 n+T(1)=\Theta(\log n)

  • Θ(1)\Theta(1): 호출 횟수가 n에 따라 늘어나므로 상수 시간이 아니다.
  • Θ(n)\Theta(n): x를 n번 곱하는 단순 반복 방식의 복잡도이다.
  • Θ(nlog⁡n)\Theta(n \log n): 호출당 작업이 상수이고 호출 횟수가 로그 수준이므로 해당하지 않는다.

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

이어서 풀어보기

[7급 국가직 자료구조론] 14년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기