2장. 컴퓨터 알고리즘 개요(2)

[ 목차 ]

1. 컴퓨터 알고리즘의 분석

2. 점근적 표기법

 

1. 컴퓨터 알고리즘의 분석

1) 수행시간 분석

  1] 특정 기계에서 수행시간을 측정하는 것은 공정하지 않음

  2] 따라서 조건이 동일한 특정 기계에서 모든 알고리즘의 수행시간을 측정해야 하나 비현실적

  3] 수행연산의 횟수를 비교하는 방식으로 성능을 분석

  4] 수행시간은 입력으로 크기가 커질수록 시간이 많이 걸리기 때문에 수행시간은 입력크기 n에대한 함수로 표현

  5] 종합하면, 공정하고 공평한 비교를 위해 점근적 표기법에 의해 기술

2) 성능 분석의 비교대상

  1] 산술 연산 : add, multiply, exponent, modurar, ...

  2] 데이터 입출력 : copy, move, save, load, ...

  3] 제어 연산 : if, while, register, ...

 

2. 점근적 표기법

1) O-notation 빅오 표기 : 함수가 느려진다 하더라도 주어진 기준 함수보다는 항상 빠름

 

2) Ω-notation 오메가 표기 : 함수가 빨라진다 하더라도 주어진 기준 함수보다는 빨라질 수 없음

 

3) θ-notation 세타 표기 : 1과 2가 합쳐진 것으로, 가장 정확