알고리즘 실행시간 측정

알고리즘의 실행시간을 측정하는 방법에는 크게 2가지가 있다
1. 점근적 분석 방법
2. 실제 시간 측정

방법1) 점근적 분석 방법

점근적 분석 방법
: Big-Oh값을 구하는 이론적 방식
: 이론적 방식에 의해 측정할 수 있음

방법2) 실제 시간 측정

실제 시간 측정
: 알고리즘 실행에 소요되는 cpu time 측정
: 라이브러리를 이용하여 측정

clock()

일반적인 시간 측정함수 clock()을 사용하면 시간이 정밀하게 나오지 않는 문제점

QueryPerformanceCounter()

이 함수를 이용하면 정밀한 시간 출력 가능

사용방법
1. 헤더파일

#include <windows.h>

2. LARGE_INTEGER 변수 선언
3. QueryPerformanceFrequency() 함수를 통해 타이머의 주파수를 변수에 저장
4. 시간을 측정하고 싶은 작업 전후에 QueryPerformanceCounter() 호출하고 그 반환값들을 이용하여 계산, 출력

사용 예시

#include <stdio.h>
#include <Windows.h>
int main(void){
	LARGE_INTEGER ticksPerSec;
	LARGE_INTEGER start, end, diff;
    
	QueryPerformanceFrequency(&ticksPerSec);
	QueryPerformanceCounter(&start);
	//시간을 측정하고 싶은 작업 예 함수 호출 을 이곳에 삽입
	QueryPerformanceCounter(&end);
    
	// 측정값으로부터 실행시간 계산
	diff.QuadPart = end.QuadPart start.QuadPart; – 
	printf("time: %.12f sec\n\n", ((double)diff.QuadPart/(double)ticksPerSec.QuadPart));
    
	return 0;
}

작동 원리

메인보드에 고해상도 타이머가 존재하는데
이를 이용하여 특정 실행 시점들의 CPU 클럭수들을 얻어온 후 그 차이를 이용하여 작업 시간을 구한다.
clock()함수와 달리 1us 이하의 시간까지 측정 가능

QueryPerformanceFrequency(): 타이머의 주파수(초당진동수)를 얻는 함수
QueryPerformanceCounter(): 타이머의 CPU 클럭수를 얻는 함수

작업 전 후의 클럭수 차를 주파수로 나누면 작업시간(초,sec) 알 수 있고,
ms 단위로 출력하기 위해서는 1,000을 곱*하면 된다

Clock() 함수와 비교

clock(): 초당 1,000번의 측정을 통해 1ms 시간 측정 가능
QueryPerformanceCounter(): 초당 10,000,000번의 측정으로 0.1us시간까지 측정 가능

초당클럭수는 time.h를 헤더로 추가한 후 CLOCKS_PER_SEC을 출력하여 알 수 있고,
타이머의 주파수는 QueryPerformanceFrequency()를 통해 알 수 있다.