자료구조_08. 시간복잡도

 

 

알고리즘의 성능 분석

• 실행 시간을 측청하는 방법
  
  • 두개의 알고리즘의 실제 실행 시간을 측정하는 것
  • 실제로 구현하는 것이 필요
  • 동일한 하드웨어를 사용해야함
  • 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 << “초입니다”;
}

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

알고리즘 A	알고리즘 B	알고리즘 C
sum ←n*n;	sum ← 0;   for i ← 1 to n do      sum ←sum + n;	sum ← 0;   for i←1 to n do     for j←1 to n do       sum ←sum + 1;

 

	알고리즘 A	알고리즘 B	알고리즘 C
대입 연산	1	n+1	n^2+1
덧셈연산		n	n*2
곱셈연산	1
전체 연산수	2	2n+1	2n^2+1

 

빅오 표기법

 

• 차수가 가장 큰 항이 가장 영향을 크게 미치고 다른 항들은 상대적으로 무시될 수 있음
• 가장 빠르게 증가하는 항만을 고려하는 표기법입니다.
• 함수의 상한만을 나타내게 됩니다
• 예: 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)인 알고리즘을 설계