<C++> 9. 시간 복잡도

알고리즘의 성능분석

(1) 실행 시간을 측정하는 방법

• 두 개의 알고리즘의 실제 실행 시간을 측정하는 것
• 실제로 구현하는 것이 필요
• 동일한 하드웨어를 사용하여야 함

• clock 함수 사용: clock_t clock(void);
  - 호출되었을 때의 시스템 시각 반환
  - CLOCKS_PER_SEC 단위
  - 실행 시간 측정 프로그램 예

#include <iostream>
#include <ctime> /* C 헤더파일 <time.h>을 포함하는 것과 동일 */
void main( void )
{
	clock_t start, finish;
	double duration;
	start = clock();
	// 실행 시간을 측정하고자 하는 코드....
	finish = clock();
	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	cout << duration << “초입니다”;
}

(2) 알고리즘의 복잡도를 분석하는 방법

• 직접 실행하지 않고서도 수행 시간을 분석하는 것
• 알고리즘이 수행하는 연산의 횟수를 측정하여 비교
• 동일한 기능을 수행할 때, 일반적으로 복잡도가 낮을수록 좋은 알고리즘
• 공간 복잡도 분석 : 수행 시 필요로 하는 메모리 공간 분석
• 시간 복잡도 분석 : 수행 시간 분석
  - 수행 시간 : 최악의 경우의 입력에 대한 기본 연산(산술, 대입, 비교, 이동)
  의 횟수
  
  
  
• n을 n번 더하는 문제

 

 

---

빅오 표기법

• 차수가 가장 큰 항이 가장 영향을 크게 미치고 다른 항들은 상대적으로 무시될 수 있음
• 가장 빠르게 증가하는 항만을 고려하는 표기법입니다.
• 함수의 상한만을 나타내게 됩니다
• 예: T(n) = n^2 + n + 1 = > O(n^2)
  n=1일때 : T(n) = 1 + 1 + 1 = 3 (33.3%)
  n=10일때 : T(n) = 100 + 10 + 1 = 111 (90%)
  n=100일때 : T(n) = 10000 + 100 + 1 = 10101 (99%)
  n=1,000일때 : T(n) = 1000000 + 1000 + 1 = 1001001 (99.9%)

요구사항에 따라 적절한 알고리즘 설계하기

• 문제에서 가장 먼저 확인해야 하는 내용은 시간제한(수행시간 요구사항)
• 시간제한이 1초인 문제를 만났을 때, 일반적인 기준
  - N의 범위가 500인 경우: 시간 복잡도가 O(N^3)인 알고리즘을 설계
  - N의 범위가 2,000인 경우: 시간 복잡도가 O(N^2)인 알고리즘을 설계
  - N의 범위가 100,000인 경우: 시간 복잡도가 O(NlogN) 인 알고리즘을 설계
  - N의 범위가 10,000,000인 경우: 시간 복잡도가 O(N)인 알고리즘을 설계