- 1 -
데이터 구조 1 실습 (2주차)
2021. 3. 10 [문제 1] 빅오 표기법을 정의하라.
[문제 2] 다음 시간복잡도 함수를 빅오 표기법으로 나타내라. 그 이유를 주라.
a. T(n) = 5n + 3
b. T(n) = 2n3 + 3n + 10
[문제 3] 다음 각 함수에 대해서 연산 회수를 연산 유형별로 구하여 시간 복잡도 함수 T(n)을 계산하고, 이 를 빅오 표기법으로 나타내라. 단, 루프 제어에 관련된 연산을 제외하라. (루프제어연산을 포함시킨 경우와 그렇지 않은 경우를 비교하라)
a.
int fun_1(int a[], int n) { int sum = 0;
for (i = 0; i< n; i++) if a[i] > 100
sum += 1;
return sum;
}
c.int fun_3(int a[], int n) { int sum = 0;
for (i = 0; i< n; i++) for(j = 0; j<n; j++)
for (k = 0; k<n; k++) if a[i] > 100
sum += 1;
return sum;
}
[문제 4] 다음에서 개략적으로 작성된 main() 함수에 기반하여 문제 3의 각 함수의 실행시간을 측정하여 아 래 테이블을 완성하라. 또한, 이 테이블을 이용하여 n 대비 실행시간을 그래프로 나타내라.
b. int fun_2(int a[], int n) { int sum = 0;
for (i = 0; i< n; i++) for (j=0; j<n; j++) if a[i] > 100
sum += 1;
return sum;
}
- 2 -
#include <time.h>
int main()
{ unsigned long int sum;
int n;
clock_t start, end;
double elapsed;
// 함수 매개변수 n을 입력 // 함수의 실행 소요 시간 측정 start = clock();
sum = fun_1(n); // 매개변수 배열을 제외 => 함수 코드에서 조건문 삭제.
end = clock();
// 소요 시간을 msec 단위로 출력 return 0;
}
a. 실행 시간 측정 결과
n 500 1,000 1,500 2,000 2,500
fun_1()
fun_2()
fun_3()
b. 실행시간 결과를 그래프로 표현
