알고리즘의 성능분석
(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) 알고리즘의 복잡도 를 분석하는 방법
직접 실행하지 않고서도 수행 시간을 분석하는 것
알고리즘이 수행하는 연산의 횟수 를 측정하여 비교
동일한 기능을 수행할 때, 일반적으로 복잡도가 낮을수록 좋은 알고리즘
공간 복잡도 분석 : 수행 시 필요로 하는 메모리 공간 분석시간 복잡도 분석
수행 시간: 최악의 경우의 입력에 대한 기본 연산(산술, 대입, 비교, 이동)의 횟수
빅오 표기법
차수가 가장 큰 향이 가장 영향을 크게 미치고 다른 향들은 상대적으로 무시될 수 있음
가장 빠르게 증가하는 항만을 고려하는 표기법이다.
함수의 상한만을 나타나게 된다.
예: T(n) = n² + n + 1 = > O(n²)
속도 순위표와 연산의 횟수 그래프
연습 문제
<문제1>
01 다음 알고리즘의 시간 복잡도를 빅오 표기법으로 나타내시오
02 다음 알고리즘의 시간 복잡도를 빅오 표기법으로 나타내시오
03 다음 알고리즘의 시간 복잡도를 빅오 표기법으로 나타내시오
<문제2>
<문제3>
요구사항에 따라 적절한 알고리즘 설계하기
문제에서 가장 먼저 확인해야 하는 내용은 시간제한(수행시간 요구사항)
