알고리즘 문제풀이 시간 복잡도 예상하기 및 시간 측정 방법

입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해, 1초 당 반복문 수행 횟수가 1억($10^8$)을 넘어가면 시간 제한을 초과할 가능성이 있다.

종만북

​

위 근사치를 이용하면 간단하게 입력의 크기와 제한시간으로 정답 알고리즘의 복잡도를 대략적으로나마 예측해 볼 수 있습니다.

​문제에서 가장 먼저 확인해야하는 내용은 시간제한(수행시간 요구사항)입니다.

 

시간제한이 1초인 문제를 만났을 때, 일반적인 기준은 다음과 같습니다.

입력이 10,000,000 개의 경우: O(N) 알고리즘

입력이 50,000 개인 경우: O(N * log N) 알고리즘

입력이 10,000 개인 경우: O(N * N) 알고리즘

입력이 400개: O(N * N * N) 알고리즘

​

거꾸로 이야기하면 입력이 100개 이하라면 대체로 어떤 알고리즘을 써도 풀릴 가능성이 높고, 입력이 매우 작은 경우는 완전탐색으로도 문제를 풀 수 있을 가능성이 높다는 이야기겠죠.

 

---

Header: <ctime>
clock_t  clock(void);
: clock() 함수는 프로그램의 실행 시작으로부터 경과된 시간을 clock ticks 수로 반환합니다.
단위는 clock tick이지만 ms와 동일합니다. 즉 ms단위를 정수형으로 반환합니다.
ctime에 정의되어있는  CLOCKS_PER_SEC과 같이 사용하면 sec(초) 단위로 출력할 수 있습니다. 

더 정밀하게 측정하고 싶다면 chrono 라이브러리를 참고하세요.

 

clock_t 타입

 

ctime

 

---

Preview)

// 측정 시작 위치
clock_t startTime = clock();

/*
    측정할 코드
*/

// 측정 종료 위치
clock_t endTime = clock();

// 측정 시간 계산 (ms단위)
clock_t elapsed = endTime - startTime;

// Second로 변환
double timeInSecond = (double)(elapsed / CLOCKS_PER_SEC);

 

 

Example)

#include <iostream>
#include <ctime>    /* clock_t, clock, CLOCKS_PER_SEC */
#include <vector>

using std::cout;
using std::string;
using std::vector;

int main(void)
{
	vector<string> vec(100000, "bonjour");
	vector<string> tmp;

	// 시작 시간
	clock_t startTime = clock();
	
	// 시간 측정할 수행 코드
	for (vector<string>::size_type i = 0; i != vec.size(); ++i)
	{
		tmp.push_back(vec[i]);
	}

	// 종료 시간
	clock_t endTime = clock();

	// Millisecond
	clock_t elapsed = endTime - startTime;

	// Second
	double timeInSecond = (double)(elapsed / CLOCKS_PER_SEC); 

	cout << "Elapsed: " << timeInSecond << "s(" << elapsed << "ms)" << "\n";

	return 0;
}