다음은 같은 기능을 수행하는 두 함수를 구현한 C 코드이다. 각 함수의… | [7급 국가직 자료구조론] 26년 1회차 기출문제 상세 페이지

다음은 같은 기능을 수행하는 두 함수를 구현한 C 코드이다. 각 함수의 시간 복잡도를 바르게 연결한 것은?
double p1(double x, int n) {
   int i;
   double result = 1.0;

   for(i = 0; i < n; i++)
      result = result * x;
   return result;
}

double p2(double x, int n) {
   if(n == 0)
      return 1;
   else if((n % 2) == 0)
      return p2(x * x, n/2);
   else
      return x * p2(x * x, (n - 1)/2);
}
p1 함수 p2 함수

$O(n)$ $O(1)$

$O(n)$ $O(\log n)$

$O(2^n)$ $O(n^2)$

$O(\log n)$ $O(n\log n)$

p1은 $O(n)$, p2는 $O(\log n)$이다.
p1은 for문이 $n$번 돌며 곱셈을 반복한다. p2는 호출마다 지수를 절반($n/2$ 또는 $(n-1)/2$)으로 줄이는 분할 정복 거듭제곱이라 호출 깊이가 $\log_2 n$에 비례한다.
p2를 상수 시간으로 본 연결은 지수가 0이 될 때까지 재귀가 반복되는 점을 무시한 것이다.
$O(2^n)$·$O(n^2)$ 연결은 두 함수 모두 과대평가한 것이다.
$O(\log n)$·$O(n\log n)$ 연결은 단순 반복인 p1을 과소평가하고 p2를 과대평가한 것이다.