다음은 x^n을 구하는 알고리즘이다. 이 알고리즘의 시간 복잡도는? (… | [7급 국가직 자료구조론] 14년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 14년 1회차
다음은 을 구하는 알고리즘이다. 이 알고리즘의 시간 복잡도는? (단, 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
2
3
4
해설
이 알고리즘의 시간 복잡도는 이다.
재귀 호출마다 지수 n이 n/2 또는 (n-1)/2로 절반씩 줄고, 각 호출은 비교·곱셈 같은 상수 시간 작업만 한다.
- : 호출 횟수가 n에 따라 늘어나므로 상수 시간이 아니다.
- : x를 n번 곱하는 단순 반복 방식의 복잡도이다.
- : 호출당 작업이 상수이고 호출 횟수가 로그 수준이므로 해당하지 않는다.
오류나 개정된 내용이 보이면 알려주세요