big-o, time complexity, adt 문제

목차

1. Big-O 의 정의에 따라 다음을 증명하시오.
2. 다음 프로그램의 time complexity를 ‘+’ 연산의 총 수로 나타내고, Big-O로 표현하시오.
3. (Programming) Time complexity, 강의 자료에 소개된 selection sort 알고리즘을 구현하고 size 1000, 2000, 5000, 10000, 20000, 50000, 100000 인 random number list에 대하여 실행 시간을 측정하시오. 측정된 시간을 selection sort 알고리즘의 이론적인 time complexity와 비교하여 설명하시오.
4. (Programming) ADT, 어떤 application에서는 평면상의 여러 가지 도형을 다룬다. 아래와 같은 프로그램이 가능하도록 점(point), 선분(line), 사각형(rect), 원(circle)을 struct를 이용하여 새로운 데이터 타입으로 정의하고, 각각의 생성(make_point, make_line, make_rect), 선분의 길이 계산(line_length), 사각형의 면적 계산(rect_area)을 수행하는 함수들을 작성하시오
5. (Programming) Stack, 수식을 표현하는 문자열을 받아서 괄호( [ ], { }, ( ) )가 올바로 사용되었는지를 검사하는 함수 check(char *exp)를 stack을 이용하여 작성하고 테스트하시오. 올바른 괄호의 사용은 1) 왼쪽과 오른쪽 괄호의 수는 같아야 하고, 2) 같은 괄호에서 왼쪽 괄호가 오른쪽 괄호보다 먼저 나와야 하며, 3)괄호 사이에는 포함 관계만 존재하여야 한다(서로 겹치지 않는다). 괄호 이외에 수식의 다른 부분에 대해서는 적합성을 검사하지 않는다.
6. (Programming) Linked list, 름차순으로 정수 데이터가 저장된 두 개의 단순연결리스트(singly linked list)로부터 두 리스트의 데이터가 오름차순으로 합병된 새로운 리스트를 생성하는 함수 void list_pointer merge(list_pointer head1, list_pointer head2)를 작성하고 테스트하시오.

본문내용

2. 다음 프로그램의 time complexity를 ‘+’ 연산의 총 수로 나타내고, Big-O로 표현하시오.
1) for (i=0;i for (j=0;j for (k=0;k c[i][j] += a[i][k]*b[k][j];

T(n)= 이므로 T(n)=O()이다.

2) while(i<=n){
sum=sum+i;
i = i*2;
}

T(n)= 이므로 T(n)=O()이다.

3. (Programming) Time complexity
강의 자료에 소개된 selection sort 알고리즘을 구현하고 size 1000, 2000, 5000, 10000, 20000, 50000, 100000 인 random number list에 대하여 실행 시간을 측정하시오. 측정된 시간을 selection sort 알고리즘의 이론적인 time complexity와 비교하여 설명하시오.

random number list 작성 예시:
#include "stdlib.h"

srand(time(NULL));
for (i = 0; i < n; i++)
list[i] = rand();

시간 측정 예시:
#include "time.h"

start = clock();
selection_sort(list, MAX);
end = clock();
computation_time = (float)(end - start) / 1000;

구현한 selection sort 코드는 아래와 같다.

#include
#include
#include
#define MAX_VALUE 5000

void selectionSort(int *value, int sort) {
int i, j, indexMin, temp;
for (i = 0; i < sort-1; i++) {
indexMin = i;
for (j = i + 1; j < sort; j++) {
if (value[j] < value[indexMin])
indexMin = j;

참고자료

· 없음