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

75

2

장

알고리즘 분석

크기가

N

인 문제 인스턴스에 대한 알고리즘의 최악의 경우에서 핵심 연산의 수를 반영하는 정

확한 모델

f

(

N

)을 가질 때, 최악의 경우에

O

(

f

(

N

))으로 분류한다. 이것은 상한이다. 상응하

는 하한도 유사하게 도출해 알고리즘이 최악의 경우에 들여야 하는 최소한의 노력을 모델링할

수 있다. 표기법

Ω

(

f

(

N

))은 알고리즘의 하한의 분류를 기술하는 데 사용한다.

앞서 이진 배열 탐색을 알아보면서

while

루프는

floor

(

log

2

(

N

))+

1

보다 더 순회할 수

없음을 확인했다. 최악의 경우에

f

(

N

)=

log

(

N

)을 사용해, 이진 배열 탐색을 공식적으로

O

(

log

N

)으로 분류한다는 의미다. 이진 배열 탐색에서 최상은 무엇일까? 목푯값이

A

[

mid

]

에

서 찾아진다면 함수는

while

루프

1

회 수행 후에 바로 반환할 것이다. 문제 인스턴스의 크기에

독립적인 상수이므로, 최상의 경우에 이진 배열 탐색을

O

(

1

)으로 분류할 수 있다는 의미다.

많은 프로그래머들이 빅오 표기법을 최악의 경우에만 사용한다고 여기지만 최상과 최악의 경

우 모두 분석에 사용할 수 있다.

TIP

때때로 그리스 대문자 세타

theta

를 사용한 알고리즘 시간 복잡도

θ

(

N

log

N

)을 볼 수 있다. 이 표기법은 일반적

으로 알고리즘에 대한 평균적인 경우를 분석하는 데 사용한다. ...