알고리즘의 성능 분석

//알고리즘의 성능 분석 기법//

> 수행시간 측정

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

> 알고리즘의 복잡도 분석

• 직접 구현하지 않고서도 수행 시간을 분석하는 것
• 알고리즘이 수행하는 연산의 횟수를 측정하여 비교
• 일반적으로 연산의 횟수는 n의 함수

*시간 복잡도 분석: 수행 시간 분석

알고리즘이 문제를 해결하기 위한 시간(연산)의 횟수를 시간 복잡도라고 한다. 

<분석방법>

• 알고리즘이 이루고 있는 연산들이 몇 번이나 수행되는지를 숫자로 표시한다.
• 산술 연산, 대입 연산, 비교 연산, 이동 연산의 기본적인 연산 ->수행시간이 입력이 크기에 따라 변하면 안됨

• 알고리즘이 수행하는 연산의 개수를 계산하여 두 개의 알고리즘을 비교한다.
• 연산의 수행횟수는 고정된 숫자가 아니라 입력의 개수 n에 대한 함수를 시간복잡도 함수라고 하고 T(n)이라고 표기

[복잡도 분석의 예]

*공간 복잡도 분석: 수행시 필요로 하는 메모리 공간 분석

* clock함수 : 호출 되었을 때의 시스템의 시각을 CLOCKS_PER_SEC단위로 변환

//빅오 표기법//

연산의 횟수를 대략적(점근적)으로 표기한 것을 빅오 표기법이라고한다. 

두개의 함수 f(n)과 g(n)이 주어졌을 때, 모든 n>= n(0)에 대하여 |f(n)|<=c|g(n)|을 만족하는 2개의 상수 c와 n0가 존재하면 f(n)= O(g(n))임

빅오는 함수의 상한으로 표시한다. //ex)n>=5 이면 2n+1 < 10n 이므로 2n+1 =O(n)