다음 C 코드에서 사용한 재귀 알고리즘의 시간 복잡도는? (단, n은 … | [7급 국가직 알고리즘] 24년 1회차 기출문제 상세 페이지

1[7급 국가직 알고리즘] 24년 1회차

다음 C 코드에서 사용한 재귀 알고리즘의 시간 복잡도는? (단, n은 배열의 크기이다)int S(int A[ ], int n){
    if( n <= 0 )  return 0;
    else return A[n-1] + S(A, n/2);
}

 $\Theta(\log n)$

 $\Theta(n)$

 $\Theta(n\log n)$

 $\Theta(n^2)$

해설

이 재귀 알고리즘의 시간 복잡도는  $\Theta(\log n)$ 이다.
호출 한 번마다 덧셈 하나의 상수 작업을 하고, 크기를 절반으로 줄여 한 번만 재귀하므로 점화식은  $T(n) = T(n/2) + \Theta(1)$ 이다.
n이 0 이하가 될 때까지 절반씩 줄어드는 횟수는 약  $\log_2 n$ 회이므로 전체 시간은  $\Theta(\log n)$ 이다.
 $\Theta(n)$ 은 크기를 1씩 줄이는 재귀  $T(n)=T(n-1)+\Theta(1)$ 의 복잡도이다.
 $\Theta(n\log n)$ 은 두 번 재귀하고 선형 작업을 하는  $T(n)=2T(n/2)+\Theta(n)$ 의 복잡도이다.
 $\Theta(n^2)$ 은 크기를 1씩 줄이며 매번 선형 작업을 하는  $T(n)=T(n-1)+\Theta(n)$ 의 복잡도이다.

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

이어서 풀어보기

[7급 국가직 알고리즘] 24년 1회차 25문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요

비슷한 기출

7급 국가직 알고리즘 기출문제 암기장 전체 보기

💬 자격증 스터디 커뮤니티헷갈리는 문제, 같이 준비하는 사람들에게 물어보세요

→