알고리즘 계산 시간 측정

---

알고리즘 계산 시간 측정 (clock() @ time.h)

** 아래 포스팅 내용 관련하여, 더 나은 방법이나 아이디어가 있으신 경우에는 댓글에 의견을 공유해주시면 감사하겠습니다.

** Source code는 C 언어로 작성되었습니다.

---

시간 복잡도 (Time complexity)

 알고리즘의 연산시간은 알고리즘의 효율성을 확인하는 대표적인 지표 중 하나로 자주 활용됩니다. 어떤 알고리즘이 다른 알고리즘보다 동일한 문제를 더 빠른 시간내에 해결할 수 있다면, 그 알고리즘이 속도면에서만큼은 다른 알고리즘 보다 더 효율적으로 구현되었다는 것을 의미합니다.

 계산 복잡도이론에서 시간 복잡도 (Time complexity) 는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다. (중략) 시간 복잡도는 기본적인 연산을 수행하는데에 어떤 고정된 시간이 걸릴 때, 알고리즘에 의해서 수행되는 기본 연산의 개수를 세어 예측할 수 있다. (위키 백과)

  

 알고리즘을 구현할 때 구현된 알고리즘의 시간 복잡도를 확인하기 위해서, 위키백과에서 언급된 것 처럼 일일이 기본 연산의 개수를 세어볼 수도 있겠지만 알고리즘이 복잡할 경우에는 이런 방법이 비효율적일 수가 있습니다. 그래서 C언어 표준 Library에서 제공하는 함수를 이용하여, 간단하게 알고리즘 시간을 비교하는 방법을 소개하고자 합니다. 

Clock()

 C언어 표준 library에서 제공하는 함수 중에 하나로, time.h내에 정의되어 있습니다. 아래 설명과 같이, 1970년 1월 1일을 기준으로 현재 시각을 나타냅니다. 

 

The value returned generally represents the number of seconds since 00:00 hours, Jan 1, 1970 UTC.

 

      따라서 시간을 측정하기 위해서는, 알고리즘 전후에 Clock값을 비교하면 됩니다. 단위는 ms로 출력됩니다.

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

void TestForLoop( void )
{
	int i;
	int a = 0;

	for (i = 0; i < 30000000; i++)
	{
		a = a + i;
	}
}

int main(void)
{
	int start = clock();
	TestForLoop();
	printf("result=%.6lf(msec)\n", (double)(clock()-start));

	return 0;
}

실행 결과는 다음과 같습니다.

 

주의 사항 :

Clock() function은 System 특성과 Compile환경에 따라서 결과가 달라질 수 있으므로, 알고리즘 간 상대 비교, 알고리즘 최적화 후 개선 수준 파악 등의 용도로 제한적으로 사용하시는 것을 추천드립니다.

 

출처 / 관련 링크

1. https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84

2. http://www.cplusplus.com/reference/ctime/time/

3. https://stackoverflow.com/questions/39935820/accuracy-of-clock-function-in-c