[C언어/자료구조] 프로그램 수행 시간 측정

[수행 시간 측정] 1부터 n까지의 합을 구하는 프로그램을 다음과 같이 3가지 방법으로 알고리즘을 만들어보고 각 알고리즘들을 실제로 구현하여 각 알고리즘의 실제수행 시간을 측정하여 이론적인 분석과 같게 나오는지를 조사해보라.

 

• 알고리즘 A: sum = n(n + 1)/2공식사용

• 알고리즘 B: sum = 1 + 2+ … + n

• 알고리즘 C: sum = (1) + (1 + 1) + (1 + 1 + 1) + …, (1 + 1 + … + 1)

 

수행 시간측정을 쉽게 하기 위하여 n을 상당히 크게 하고 중간에 고의적인 시간지연함수를 넣거나 같은 합산을 여러 번 반복하라. 각 n값에 대하여 수행 시간을 측정하여 표로 나타내라.

 

알고리즘 A 코드

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h> 

int main() {
	clock_t start, end;
	double result;
	int n, sum = 0;

	start = clock(); 

	printf("숫자를 입력해주세요\n");
	scanf_s("%d", &n);

	Sleep(3000);

	sum = n * (n + 1) / 2;
	
	end = clock();
	result = (double)(end-start) / CLOCKS_PER_SEC;

	printf("sum=%d \n", sum);
	printf("%f 초입니다. \n", result);
	return 0; 
}

 

알고리즘B 코드

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h> 

int main() {
	clock_t start, end;
	double result;
	int n, sum = 0;

	start = clock(); 


	printf("숫자를 입력해주세요\n");
	scanf_s("%d", &n);

	Sleep(3000);

	for (int i = 0; i <= n; i++) {
		sum += i;
	}
	
	end = clock();
	result = (double)(end-start) / CLOCKS_PER_SEC;

	printf("sum=%d \n", sum);
	printf("%f 초입니다. \n", result);
	return 0; 
}

 

알고리즘C 코드

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h> 

int main() {
	clock_t start, end;
	double result;
	int n, sum = 0;

	start = clock(); 


	printf("숫자를 입력해주세요\n");
	scanf_s("%d", &n);

	Sleep(3000);

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < i; j++) {
			sum += 1;
		}
	}
	
	end = clock();

	result = (double)(end-start) / CLOCKS_PER_SEC;

	printf("sum=%d \n", sum);
	printf("%f 초입니다. \n", result);

	return 0;
}

 

수행 시간 측정 결과 표

	n = 100	n = 1000	n = 10000
A	sum=5050 4.241000초	sum=500500 4.584000초	sum=50005000 5.104000초
B	sum=5050 4.059000초	sum=500500 5.001000초	sum=50005000 5.003000초
C	sum=5050 3.845000초	sum=500500 4.889000초	sum=50005000 5.481000초