다음 C 함수에 대하여 F(L, 0, n-1)를 수행할 경우 시간 복잡… | [7급 국가직 자료구조론] 07년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 07년 1회차
다음 C 함수에 대하여 F(L, 0, n-1)를 수행할 경우 시간 복잡도는?
int F(int L[], int p, int q)
{
if (p<q)
{ int r, f1, f2;
r = (p+q)/2;
f1 = 2*F(L, p, r);
f2 = 2*F(L, r+1, q);
return f1+f2;
}
else if (p == q)
return L[p]*L[p];
else
return 0;
}
1
Θ(n)\Theta(n)
2
Θ(nlog⁡n)\Theta(n\log n)
3
Θ(n2)\Theta(n^2)
4
Θ(2n)\Theta(2^n)
해설

F(L, 0, n-1)의 시간 복잡도는 Θ(n)\Theta(n)이다.

함수는 구간을 반으로 나눠 두 번 재귀 호출하고, 나머지 곱셈·덧셈은 상수 시간이다. 따라서 T(n)=2T(n/2)+cT(n)=2T(n/2)+c이다.

마스터 정리에서 nlog⁡22=nn^{\log_2 2}=n이 상수항보다 크므로 T(n)=Θ(n)T(n)=\Theta(n)이다. 재귀 트리로 보아도 호출 수는 약 2n개이다.

  • Θ(nlog⁡n)\Theta(n\log n): 단계마다 병합 같은 선형 작업이 있어야 나오는데, 이 함수는 단계마다 상수 작업뿐이다.
  • Θ(n2)\Theta(n^2): 결과값에 2를 곱하는 것은 값 계산일 뿐 호출 횟수를 늘리지 않는다.
  • Θ(2n)\Theta(2^n): 재귀 깊이는 log⁡2n\log_2 n이므로 호출 수가 지수적으로 늘지 않는다.

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

이어서 풀어보기

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