다음 C 코드의 시간 복잡도(time complexity)는?void … | [7급 국가직 자료구조론] 23년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 23년 1회차

다음 C 코드의 시간 복잡도(time complexity)는?void func(int n)
{
  int i, j, k = 0;
  for(i = 0; i < (n + 200); i++)
    for(j = 0; j < 300; j++)
      printf("k = %d\n", k++);
}

 $O(n)$

 $O(n^2)$

 $O(\log_2 n)$

 $O(n\log_2 n)$

해설

이 코드의 시간 복잡도는 $O(n)$ 이다.

바깥 루프는 $n+200$ 회, 안쪽 루프는 n과 무관하게 항상 300회 돈다. printf 실행 횟수는 $(n+200) \times 300 = 300n + 60000$ 이고, 상수 계수와 상수항을 버리면 n에 비례한다.

$O(n^2)$ : 안쪽 루프도 n에 비례해야 나오는 결과인데, 안쪽은 상수 300회다.
$O(\log_2 n)$ : 반복마다 문제 크기가 절반으로 줄어드는 구조가 아니다.
$O(n\log_2 n)$ : 로그 횟수로 도는 루프가 없으므로 해당하지 않는다.

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

이어서 풀어보기

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

비슷한 기출

7급 국가직 자료구조론 기출문제 암기장 전체 보기

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

→