다음 C 언어로 작성된 함수들의 시간 복잡도에 대한 설명으로 옳은 것은… | [7급 국가직 자료구조론] 26년 1회차 기출문제 상세 페이지

다음 C 언어로 작성된 함수들의 시간 복잡도에 대한 설명으로 옳은 것은?
void func1(int n) {
   for(int i = 0 ; i < 2 ; i++)
      for(int j = 0 ; j < n ; j++)
         printf("%d\n", j);
}

void func2(int n) {
   for(int i = 0 ; i < 100 ; i++)
      printf("%d\n", i);
}

void func3(int n) {
   if(n == 0)
      return;
   printf("%d\n", n);
      func3(n/2); ····················(가)
}

func1 함수는 이중 for 반복문으로 구성되어 시간 복잡도는 $O(n^2)$이다.

func2 함수는 for 반복문으로 구성되어 시간 복잡도는 $O(n)$이다.

func3 함수는 for 반복문이 없어 시간 복잡도는 $O(1)$이다.

(가) 문장을 func2(n/2);으로 수정할 경우, func3 함수의 시간 복잡도는 $O(1)$이다.

(가)를 func2(n/2)로 바꾸면 func3는 상수 시간 $O(1)$이 된다.
수정 후 func3는 출력 한 번과 func2 호출 한 번만 수행하는데, func2는 인자와 무관하게 100회만 반복하므로 전체가 상수 시간이다.
func1의 바깥 반복은 2회로 고정이라 $2n$번 출력, 즉 $O(n)$이지 $O(n^2)$가 아니다.
func2는 반복 횟수가 100으로 고정되어 $O(1)$이지 $O(n)$이 아니다.
func3는 반복문이 없어도 $n$을 절반씩 줄이며 재귀하므로 $O(\log n)$이다.