다음 C 언어 함수의 시간 복잡도를 빅오(O) 표기법으로 표현한 것은?… | [7급 국가직 자료구조론] 17년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 17년 1회차
다음 C 언어 함수의 시간 복잡도를 빅오(O) 표기법으로 표현한 것은? (단, n>1n > 1)
void testing(int n)
{
int i, j, sum = 0;
for (i = 0; i < n; i++)
for (j = n; j > 1; j /= 2)
sum += 1;
}
1
O(n)
2
O(n2)
3
O(nlogn)
4
O(logn)
해설

시간 복잡도는 O(n log n)이다.

바깥 반복문은 i가 0부터 n-1까지 n회 돈다. 안쪽 반복문은 j를 n에서 시작해 1보다 클 동안 절반씩 줄이므로 약 log n회 돈다. 전체 실행 횟수는 두 횟수의 곱인 약 n·log n이다.

  • O(n): 안쪽 반복의 log n배를 빠뜨린 결과이다.
  • O(n2)O(n^2): 안쪽 반복이 n회일 때의 결과인데, j는 1씩이 아니라 절반씩 줄어든다.
  • O(log n): 바깥 반복의 n회를 빠뜨린 결과이다.

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

이어서 풀어보기

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