똑똑한 코드 작성을 위한 실전 알고리즘

60

똑똑한 코드 작성을 위한 실전 알고리즘

컴퓨터 과학자는 문제 인스턴스 크기

N

에서 최상의 경우 (혹은 최악의 경우 ) 런타임 성능에

기반해 알고리즘을 분류하기 위해

빅오 표기법

Big

O notation

을 사용한다. 이름에 문자 ‘

O

’가 들

어간 이유는 함수의 상승률을

함수의 차수

order

of

function

라 부르기 때문이다. 예를 들어, 공식

4N

2

+

3N

-

5

는

N

의 가장 큰 지수가

2

이므로 ‘

2

차수’ 함수이다.

크기가

N

인 문제 인스턴스에서 알고리즘의 런타임 성능을 추정하려면 먼저 수행 횟수를 계산

해야 한다. 각 수행을 실행하는 데 드는 시간이 고정되었다고 가정하므로, 수행 횟수를 계산하

면 런타임 성능을 추정할 수 있다.

NOTE

_

T

(

N

)은 알고리즘이 크기가

N

인 문제 인스턴스를 처리하는 데 필요한 시간이다. 같은 알고리즘에

대해 최상의 경우와 최악의 경우로 정의된 다른

T

(

N

)이 있을 수 있다. 밀리초나 초 같은 시간 단위는 중요치

않다.

S

(

N

)은 알고리즘이 크기가

N

인 문제 인스턴스를 처리하는 데 필요한 저장 공간이다. 같은 알고리즘에 대해

최상의 경우와 최악의 경우로 정의된 다른

S

(

N

)이 있을 수 있다. 비트나 기가바이트 같은 공간의 단위는 중요

치 않다.

2.5

모든 수행 계산하기

목표는 알고리즘이

크기가

N

인 문제 인스턴스

를 처리하는 ...