[자료구조] 2주차 과제

1. 각 코드에 시간측정 부분을 추가하여 프로그램을 완성하고 테스트하시오.

 

[코드1]

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

 

int main()

{

int i = 0;

int j = 0;

int sum = 0;

int N;

 

clock_t start,finish;

double duration;

 

 

printf("N을 입력하세요");

printf("\n");

scanf("%d",&N);

 

start = clock();

 

 

i = N;

while (i > 1)

{

i = i / 2;

for (j = 0; j < 1000000; j++)

sum = sum + j;

}

 

finish = clock();

duration = (double)(finish - start) / CLOCKS_PER_SEC;

printf("%f 초입니다.\n", duration);

}

 

[코드2]

 

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

 

int main()

{

int i = 0;

int j = 0;

int sum = 0;

int N;

int d;

 

clock_t start,finish;

double duration;

 

 

printf("N을 입력하세요");

printf("\n");

scanf("%d",&N);

 

start = clock();

 

 

sum = 0;

d = 1;

d = d << (N-1) ;

for (i = 0; i < d; i++)

for (j = 0; j < 1000000; j++)

sum = sum + i;

 

finish = clock();

duration = (double)(finish - start) / CLOCKS_PER_SEC;

printf("%f 초입니다.\n", duration);

}

 

 

2. 실험결과에 따라 다음 표를 완성하시오.

 

[코드1의 수행시간]

N 1000000 2000000 . . . 70000000

sec 0.046000 0.048000 . . . 0.062000

 

[코드2의 수행시간] (N값을 31이하로 주어야 함. 실제 실험은 가능한 값까지 사용)

N 1 2 . . . 14 15 16

sec 0.001000 0.002000 10.846000 22.092000 43.084000

 

그 이후의 실험은 소요시간이 너무 오래 걸려 진행하지 못했습니다.

 

3. 코드1과 코드2의 Step Count를 각각 적고 빅오(O) 표기법으로 나타내시오.

 

[코드 1]

i = N;

while (i > 1) {

i = i / 2; -----> log₂ⁿ번

for (j = 0; j < 1000000; j++) ----->1000000번

sum = sum + j;

}

정답 : O(logN * 1000000) = O(logN)

 

 

 

[코드 2]

sum = 0;

d = 1;

d = d << (N-1) ;

for (i = 0; i < d; i++) ----->2^(N-1) 번

for (j = 0; j < 1000000; j++) ----->1000000번

sum = sum + i;

 

정답 : O(2^(N-1) * 1000000) = O(2^(N-1))